Capacitated Domination and Covering: A Parameterized Perspective
From MaRDI portal
Recommendations
Cites work
- A threshold of ln n for approximating set cover
- An improved approximation algorithm for vertex cover with hard capacities
- Capacitated vertex covering
- Computing small partial coverings
- Covering Problems with Hard Capacities
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1559541 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved Parameterized Upper Bounds for Vertex Cover
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- On the ratio of optimal integral and fractional covers
- Parameterized complexity of Vertex Cover variants
- Parametrized complexity theory.
- Polynomial-time data reduction for dominating set
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Treewidth. Computations and approximations
Cited in
(47)- Defensive alliances in graphs of bounded treewidth
- Parameterized complexity of length-bounded cuts and multicuts
- Capacitated domination faster than O(2ⁿ)
- Upper and lower degree-constrained graph orientation with minimum penalty
- Algorithms and complexity results for the capacitated vertex cover problem
- Iterative partial rounding for vertex cover with hard capacities
- Facility location problems: a parameterized view
- Capacitated domination: problem complexity and approximation algorithms
- Solving Capacitated Dominating Set by using covering by subsets and maximum matching
- Parameterized complexity of Vertex Cover variants
- Integer programming in parameterized complexity: five miniatures
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- Algorithmic applications of tree-cut width
- Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
- Parameterized dynamic variants of red-blue dominating set
- Structural parameterizations of the mixed Chinese postman problem
- Planar capacitated dominating set is \(W[1]\)-hard
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Integer programming in parameterized complexity: three miniatures
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Algorithmic applications of tree-cut width
- Grundy Distinguishes Treewidth from Pathwidth
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Algorithms and Data Structures
- Grundy distinguishes treewidth from pathwidth
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Exploring the gap between treedepth and vertex cover through vertex integrity
- 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
- Extended MSO model checking via small vertex integrity
- Offensive alliances in graphs
- On the complexity of some colorful problems parameterized by treewidth
- Vertex cover problem parameterized above and below tight bounds
- Guard games on graphs: keep the intruder out!
- Generalized k-center: distinguishing doubling and highway dimension
- FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
- XNLP-completeness for parameterized problems on graphs with a linear structure
- XNLP-completeness for parameterized problems on graphs with a linear structure
- Complexity of secure sets
- XALP-completeness of parameterized problems on planar graphs
- Bridging treewidth and clique-width via cograph-modular-treewidth
- Parameterized complexity of directed traveling salesman problem
- On bounded-degree vertex deletion parameterized by treewidth
- Parameterized algorithm for eternal vertex cover
This page was built for publication: Capacitated Domination and Covering: A Parameterized Perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503580)
