𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On treewidth approximations

✍ Scribed by V Bouchitté; D Kratsch; H Müller; I Todinca

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
279 KB
Volume
136
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a di erent technique, we give a O(log k) approximation algorithm for the treewidth of arbitrary graphs, where k is the treewidth of the input graph.

📜 SIMILAR VOLUMES

On treewidth approximations
On treewidth approximations
✍ Vincent Bouchitté; Dieter Kratsch; Haiko Miiller; Ioan Todinca 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 329 KB
Domino Treewidth
Domino Treewidth
✍ Hans L. Bodlaender; Joost Engelfriet 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 486 KB

We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every k, d, there exists a constant c such that a

On bounded treewidth duality of graphs
On bounded treewidth duality of graphs
✍ Ne?et?il, Jaroslav; Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 734 KB

For a graph H , the H-coloring problem is to decide whether or not an instance graph G is homomorphic to H . The H-coloring problem is said to have bounded treewidth duality if there is an integer k such that for any graph G which is not homomorphic to H , there is a graph F of treewidth k which is

A Note on Multiflows and Treewidth
A Note on Multiflows and Treewidth
✍ Chandra Chekuri; Sanjeev Khanna; F. Bruce Shepherd 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 331 KB