Capacitated domination: constant factor approximations for planar graphs

DOI10.1007/978-3-642-25591-5_51MaRDI QIDQ3104645zbMATH OpenOpenAlexFDO

Authors Mong-Jen Kao, Der-Tsai Lee

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.4606

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this problem, we are given a graph with three parameters defined on the vertex set, which are cost, capacity, and demand. The objective of this problem is to compute a demand assignment of least cost, such that the demand of each vertex is fully-assigned to some of its closed neighbours without exceeding the amount of capacity they provide. In this paper, we provide the first constant factor approximation for this problem on planar graphs, based on a new perspective on the hierarchical structure of outer-planar graphs. We believe that this new perspective and technique can be applied to other capacitated covering problems to help tackle vertices of large degrees.

Recommendations

• Capacitated domination: problem complexity and approximation algorithms
• Capacitated domination problems on planar graphs
• Approximation algorithms for the capacitated domination problem
• Capacitated Domination Problem
• Planar capacitated dominating set is \(W[1]\)-hard

Cited in

(5)

• Approximation algorithms for the capacitated domination problem
• Planar capacitated dominating set is \(W[1]\)-hard
• Capacitated domination: problem complexity and approximation algorithms
• Capacitated domination problems on planar graphs
• Capacitated Domination Problem

This page was built for publication: Capacitated domination: constant factor approximations for planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104645)