Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity

DOI10.1007/978-3-540-79228-4_16zbMath1139.68344OpenAlexW1524294733MaRDI QIDQ3502644

Jan Kratochvíl, Petr A. Golovach

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_16

zbMATH Keywords

computational complexitygraph algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Parameterized complexity of generalized domination problems ⋮ Branch and recharge: exact algorithms for generalized domination

Cites Work

• Unnamed Item
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees

This page was built for publication: Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity