𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On treewidth approximations

✍ Scribed by Vincent Bouchitté; Dieter Kratsch; Haiko Miiller; Ioan Todinca

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
329 KB
Volume
8
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On treewidth approximations
On treewidth approximations
✍ V Bouchitté; D Kratsch; H Müller; I Todinca 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 279 KB

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 arbit

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