Stream: Archive Mirror: Isabelle Users Mailing List

Topic: [isabelle] New AFP article: Tree Decomposition

view this post on Zulip Email Gateway (Aug 22 2022 at 13:17):

From: Tobias Nipkow <nipkow@in.tum.de>
Tree Decomposition
Christoph Dittmann

We formalize tree decompositions and tree width in Isabelle/HOL, proving that
trees have treewidth 1. We also show that every edge of a tree decomposition is
a separation of the underlying graph. As an application of this theorem we prove
that complete graphs of size n have treewidth n-1.

http://www.isa-afp.org/entries/Tree_Decomposition.shtml

Enjoy!
smime.p7s

view this post on Zulip Email Gateway (Aug 22 2022 at 13:31):

From: Benedikt Nordhoff <bnord01@gmail.com>
I tried to access the documents but I only get 404 errors.

Best Benedikt
Not Found

The requested URL /browser_info/current/AFP/Tree_Decomposition/outline.pdf was not found on this server.

Apache/2.4.7 (Ubuntu) Server at www.isa-afp.org Port 80

view this post on Zulip Email Gateway (Aug 22 2022 at 13:32):

From: Tobias Nipkow <nipkow@in.tum.de>
Fixed, sorry, thanks.

Tobias
smime.p7s

Last updated: Apr 20 2024 at 08:16 UTC