Parameterized complexity of generalized domination problems

DOI10.1016/j.dam.2010.11.012zbMath1241.05108OpenAlexW2064310439MaRDI QIDQ415279

Petr A. Golovach, Ondřej Suchý, Jan Kratochvíl

Publication date: 11 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.11.012

zbMATH Keywords

parameterized complexityeven setgeneralized dominationodd set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Structural Parameterizations of the Mixed Chinese Postman Problem ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth ⋮ The complexity of finding harmless individuals in social networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Sort and Search: exact algorithms for generalized domination
• Threshold dominating sets and an improved characterization of \(W[2\)]
• Perfect Code is \(W[1\)-complete]
• Linear time solvable optimization problems on graphs of bounded clique-width
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• On nowhere dense graphs
• Parametrized complexity theory.
• On the Boolean-Width of a Graph: Structure and Applications
• The Grad of a Graph and Classes with Bounded Expansion
• Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• Faster Algorithms on Branch and Clique Decompositions
• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• First order properties on nowhere dense structures
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• MOD-2 INDEPENDENCE AND DOMINATION IN GRAPHS
• Parameterized Complexity of Generalized Domination Problems