Parameterized complexity of generalized domination problems
From MaRDI portal
Publication:415279
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
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
