Linear-time algorithms for partial k-tree complements

DOI10.1007/S004530010019MaRDI QIDQ1578411zbMATH OpenOpenAlexFDO

Authors D. Kaller, T. Shermer, Arvind Kumar Gupta

Publication date 13 February 2001

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004530010019

zbMATH Keywords

complement graphsgraph factoringmonadic second-order logicpartial \(k\)-treestreewidth

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

It is well known that many problems that are NP-hard for general graphs become linear time solvable when restricted to graphs of bounded treewidth, or, equivalently, partial \(k\)-trees. This is for instance true for all problems that can be expressed in monadic second-order logic, or extensions, like counting MSOL, where quantification can be done over (sets of) vertices and edges. In this paper, the variant where quantification over sets of non-edges can be done is considered. The paper explores relations with complements of partial \(k\)-trees. It analyses some concrete problems, including \(\chi_t\)-coloring, \(f\)-factoring, and Hamiltonian circuit, for partial \(k\)-trees or their complements.

Recommendations

• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Regular-factors in the complements of partial k-trees
• Edge-Coloring Partialk-Trees
• Vertex partitioning problems on partial k-trees

Cited in

(2)

• scientific article; zbMATH DE number 4024784 (Why is no real title available?)
• Regular-factors in the complements of partial k-trees

This page was built for publication: Linear-time algorithms for partial \(k\)-tree complements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1578411)