Capacitated domination: problem complexity and approximation algorithms

DOI10.1007/s00453-013-9844-6zbMath1311.68189OpenAlexW2095525633MaRDI QIDQ2345937

Mong-Jen Kao, Der-Tsai Lee, Han Lin Chen

Publication date: 21 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9844-6

zbMATH Keywords

graph theorydominating setapproximation algorithmscapacitated domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (7)

Tight approximation for partial vertex cover with hard capacities ⋮ Exact capacitated domination: on the computational complexity of uniqueness ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Uniqueness of \(DP\)-Nash subgraphs and \(D\)-sets in weighted graphs of Netflix games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Capacitated domination problem
• On the complexity of some colorful problems parameterized by treewidth
• Approximation algorithms for combinatorial problems
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• Improved approximation algorithms for capacitated facility location problems
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• On embedding an outer-planar graph in a point set
• Parametrized complexity theory.
• An improved approximation algorithm for vertex cover with hard capacities
• Simpler Linear-Time Kernelization for Planar Dominating Set
• Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
• Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
• Capacitated Domination: Constant Factor Approximations for Planar Graphs
• A threshold of ln n for approximating set 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
• Capacitated Domination and Covering: A Parameterized Perspective
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Capacitated Domination Faster Than O(2 n )
• Polynomial-time data reduction for dominating set
• Approximation Algorithms for the Capacitated Domination Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Efficient Planarity Testing
• Approximation algorithms for NP-complete problems on planar graphs
• Capacitated vertex covering
• Domination in Graphs Applied to Electric Power Networks
• A linear time algorithm for finding tree-decompositions of small treewidth
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• Computing and Combinatorics

This page was built for publication: Capacitated domination: problem complexity and approximation algorithms