Parameterized complexity of generalized domination problems
From MaRDI portal
Publication:415279
DOI10.1016/j.dam.2010.11.012zbMath1241.05108MaRDI 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
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH, A width parameter useful for chordal and co-comparability graphs, Subexponential fixed-parameter algorithms for partial vector domination, Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications, The complexity of finding harmless individuals in social networks, The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth, Structural Parameterizations of the Mixed Chinese Postman Problem
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
