Planar Capacitated Dominating Set Is W[1]-Hard

DOI10.1007/978-3-642-11269-0_4zbMath1273.68145OpenAlexW97328970WikidataQ59567702 ScholiaQ59567702MaRDI QIDQ3656850

Daniel Lokshtanov, Eelko Penninkx, Hans L. Bodlaender

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_4

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, On the parameterized complexity of some optimization problems related to multiple-interval graphs, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, Generalized \(k\)-center: distinguishing doubling and highway dimension, Capacitated domination faster than \(O(2^n)\), Solving Capacitated Dominating Set by using covering by subsets and maximum matching, Paths of bounded length and their cuts: parameterized complexity and algorithms, Parameterized Dynamic Variants of Red-Blue Dominating Set, On complexities of minus domination, Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Algorithmic Applications of Tree-Cut Width, Kernelization: New Upper and Lower Bound Techniques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterized complexity of multiple-interval graph problems
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Parametrized complexity theory.
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Capacitated Domination and Covering: A Parameterized Perspective
• Polynomial-time data reduction for dominating set
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs