Loading...
report
An introduction to treewidth
Bronner, Daniela
•
Ries, Bernard
2006
The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. A lot of problems, which are in general $NP$-complete, can be solved in polynomial time for graphs with small treewidth. In the first part of this paper we present three different definitions of treewidth and we show their equivalence. The second part consists of an overview of the complexity status of the treewidth problem as well as of algorithmics results. We also discuss a polynomial time algorithm for computing the treewidth of circle graphs.
Loading...
Name
reportfinal.ps
Access type
openaccess
Size
388.16 KB
Format
Postscript
Checksum (MD5)
2be63c9dcd764a9ac40d49815cc6628b