@inproceedings{ec0b8bd5cdf94f8982e7ab2f082e60a9,
title = "Capacitated domination problem",
abstract = "We consider a generalization of the well-known domination problem on graphs. The (soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demand of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies that the demand of each vertex in V is met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a 3/2-approximation algorithm. We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.",
author = "Kao, {Mong Jen} and Liao, {Chung Shou}",
year = "2007",
doi = "10.1007/978-3-540-77120-3_24",
language = "English",
isbn = "9783540771180",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "256--267",
booktitle = "Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings",
address = "Germany",
note = "null ; Conference date: 17-12-2007 Through 19-12-2007",
}