1995 | ReviewPaper | Buchkapitel
Domino treewidth
Extended abstract
verfasst von : Hans L. Bodlaender, Joost Engelfriet
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 k,d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most C k,d The domino treewidth of a tree can be computed in O(n2 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 ξ N, and hence the problem for fixed k is unlikely to be solvable in O(nc), where c is a constant, not depending on k.