✦ LIBER ✦

Domino Treewidth

✍ Scribed by Hans L. Bodlaender; Joost Engelfriet

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 486 KB
Volume: 24
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0854

No coin nor oath required. For personal study only.

✦ Synopsis

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 graph with treewidth at k, d most k and maximum degree at most d has domino treewidth at most c . The k, d Ž 2

. domino treewidth of a tree can be computed in O n log n time. There exist polynomial time algorithms thatᎏfor fixed kᎏdecide whether a given graph G has domino treewidth at most k. If k is not fixed, this problem is NP-complete.

w x The domino treewidth problem is hard for the complexity classes W t for all Ž c . t g N, and hence the problem for fixed k is unlikely to be solvable in O n time, where c is a constant, not depending on k.

📜 SIMILAR VOLUMES

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

Treewidth: Computational Experiments

✍ Arie M. C.A. Koster; Hans L. Bodlaender; Stan P.M. van Hoesel 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 250 KB

On treewidth approximations

✍ Vincent Bouchitté; Dieter Kratsch; Haiko Miiller; Ioan Todinca 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 329 KB

Approximation Algorithms for Treewidth

✍ Eyal Amir 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 745 KB

Equitable list coloring and treewidth

✍ Michael J. Pelsmajer 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a __list coloring__ is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is __equitable__ if each color appears on at mo

Treewidth of Chordal Bipartite Graphs

✍ T. Kloks; D. Kratsch 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 743 KB

Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one. We present a polynomial time algorithm for the exact computa