Capacitated domination: problem complexity and approximation algorithms
type: Item
instance of: scholarly article
title: Capacitated domination: problem complexity and approximation algorithms
zbMATH Open document ID: 1311.68189
author: Mong-Jen Kao
author: Hanlin Chen
author: Der-Tsai Lee
published in: Algorithmica
publication date: 2015-05-21T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6438348
zbMATH Keywords: capacitated domination
zbMATH Keywords: approximation algorithms
zbMATH Keywords: dominating set
zbMATH Keywords: graph theory
MaRDI profile type: Publication
full work available at URL: s00453-013-9844-6
OpenAlex ID: W2095525633
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: Polynomial-time data reduction for dominating set
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: A linear time algorithm for finding tree-decompositions of small treewidth
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: On embedding an outer-planar graph in a point set
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: Improved approximation algorithms for capacitated facility location problems
cites work: Covering Problems with Hard Capacities
cites work: Capacitated Domination Faster Than O(2 n )
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Capacitated Domination and Covering: A Parameterized Perspective
cites work: A threshold of ln n for approximating set cover
cites work: On the complexity of some colorful problems parameterized by treewidth
cites work: Parametrized complexity theory.
cites work: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
cites work: An improved approximation algorithm for vertex cover with hard capacities
cites work: Q4198056
cites work: Capacitated vertex covering
cites work: Linear Problem Kernels for NP-Hard Problems on Planar Graphs
cites work: Simpler Linear-Time Kernelization for Planar Dominating Set
cites work: Q4368728
cites work: Domination in Graphs Applied to Electric Power Networks
cites work: Approximation Algorithms for the Set Covering and Vertex Cover Problems
cites work: Efficient Planarity Testing
cites work: Approximation algorithms for combinatorial problems
cites work: Q5743430
cites work: Approximation Algorithms for the Capacitated Domination Problem
cites work: Capacitated Domination: Constant Factor Approximations for Planar Graphs
cites work: Capacitated domination problem
cites work: Treewidth. Computations and approximations
cites work: Computing and Combinatorics
cites work: Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
cites work: Q5710169
cites work: Q3898496
cites work: Q4526991
cites work: Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
cites work: Q4782696
cites work: A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
DOI: 10.1007/S00453-013-9844-6
description: scientific article