TY - GEN
T1 - Capacitated domination
T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011
AU - Kao, Mong Jen
AU - Lee, D. T.
N1 - Funding Information:
Supported in part by the National Science Council, Taiwan, under Grants NSC99-2911-I-002-055-2, NSC98-2221-E-001-007-MY3, and NSC98-2221-E-001-008-MY3.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84055200175&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25591-5_51
DO - 10.1007/978-3-642-25591-5_51
M3 - Conference contribution
AN - SCOPUS:84055200175
SN - 9783642255908
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 494
EP - 503
BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Y2 - 5 December 2011 through 8 December 2011
ER -