caa a22 4500 445804696 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9336-x doi (NATIONALLICENCE)springer-10.1007/s00453-009-9336-x Capacitated Domination Problem [Elektronische Daten] [Mong-Jen Kao, Chung-Shou Liao, D. Lee] 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 demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. 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 polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs. Springer Science+Business Media, LLC, 2009 Algorithm nationallicence Domination nationallicence Facility location nationallicence Kao Mong-Jen Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan aut Liao Chung-Shou Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan aut Lee D. Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan aut Algorithmica Springer-Verlag 60/2(2011-06-01), 274-300 0178-4617 60:2<274 2011 60 453 https://doi.org/10.1007/s00453-009-9336-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9336-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kao Mong-Jen Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan aut NATIONALLICENCE 700 1- Liao Chung-Shou Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan aut NATIONALLICENCE 700 1- Lee D. Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 274-300 0178-4617 60:2<274 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer