𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Treewidth: Computational Experiments

✍ Scribed by Arie M. C.A. Koster; Hans L. Bodlaender; Stan P.M. van Hoesel

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

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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 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

On treewidth approximations
On treewidth approximations
✍ Vincent BouchittΓ©; Dieter Kratsch; Haiko Miiller; Ioan Todinca πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 329 KB