article · 1994

Domino treewidth

Hans L. Bodlaender, Joost Engelfriet

Cited by 0Abstract and details only

Abstract

We consider a special variant of tree-decompositions, called domino treedecompositions, 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 ck;d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most ck;d. The domino treewidth of a tree can be computed in O(n 2 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. The domino treewidth problem is hard for the complexity classes W [t] for all t 2 N, and hence the problem for fixed k is unlikely to be solvable in O(n c), where c is a constant, not depending on k.

Cite this paper

APA 7

Bodlaender, H. L., & Engelfriet, J. (1994). Domino treewidth.

MLA 9

Bodlaender, Hans L., and Joost Engelfriet. “Domino treewidth.” 1994.

Chicago

Bodlaender, Hans L., and Joost Engelfriet. 1994. “Domino treewidth.”

Harvard

Bodlaender, H.L. and Engelfriet, J. (1994) ‘Domino treewidth’.

BibTeX

@article{bodlaender1994domino,
  title = {{Domino treewidth}},
  author = {Bodlaender, Hans L. and Engelfriet, Joost},
  year = {1994}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.