Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs

DOI10.1007/978-3-540-74839-7_1zbMath1141.68530OpenAlexW1848715483MaRDI QIDQ3508549

Jan Kratochvíl, Petr A. Golovach

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_1

zbMATH Keywords

graph algorithmsComputational complexity

Mathematics Subject Classification ID

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

Related Items (5)

A width parameter useful for chordal and co-comparability graphs ⋮ Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity ⋮ A note on bipartite graphs whose [1,k-domination number equal to their number of vertices] ⋮ Parameterized complexity of generalized domination problems ⋮ Branch and recharge: exact algorithms for generalized domination

Cites Work

• Unnamed Item
• Unnamed Item
• A complete complexity classification of the role assignment problem
• On the complexity of H-coloring
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Bi‐arc graphs and the complexity of list homomorphisms
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems

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