TY - GEN

T1 - Capacitated domination

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 -