Capacitated Domination and Covering: A Parameterized Perspective
From MaRDI portal
Publication:3503580
DOI10.1007/978-3-540-79723-4_9zbMath1142.68371OpenAlexW1500603002MaRDI QIDQ3503580
Yngve Villanger, Daniel Lokshtanov, Michael Dom, Saket Saurabh
Publication date: 5 June 2008
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-79723-4_9
Analysis of algorithms and problem complexity (68Q25) 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 ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Defensive alliances in graphs of bounded treewidth ⋮ Structural Parameterizations of the Mixed Chinese Postman Problem ⋮ Parameterized Power Vertex Cover ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Problems hard for treewidth but easy for stable gonality ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ Unnamed Item ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Extended MSO model checking via small vertex integrity ⋮ Vertex cover problem parameterized above and below tight bounds ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ Guard games on graphs: keep the intruder out! ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ Facility location problems: a parameterized view ⋮ Complexity of secure sets ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Parameterized algorithm for eternal vertex cover ⋮ Algorithmic Applications of Tree-Cut Width ⋮ The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth ⋮ Planar Capacitated Dominating Set Is W[1-Hard] ⋮ Offensive alliances in graphs ⋮ Capacitated domination: problem complexity and approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Computing small partial coverings
- On the ratio of optimal integral and fractional covers
- Treewidth. Computations and approximations
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Parameterized complexity of Vertex Cover variants
- Parametrized complexity theory.
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- An improved approximation algorithm for vertex cover with hard capacities
- A threshold of ln n for approximating set cover
- Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Covering Problems with Hard Capacities
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Polynomial-time data reduction for dominating set
- Capacitated vertex covering
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Improved Parameterized Upper Bounds for Vertex Cover
This page was built for publication: Capacitated Domination and Covering: A Parameterized Perspective
