Capacitated domination problem

Mong Jen Kao*, Chung Shou Liao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

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.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
PublisherSpringer Verlag
Pages256-267
Number of pages12
ISBN (Print)9783540771180
DOIs
StatePublished - 2007
Event18th International Symposium on Algorithms and Computation, ISAAC 2007 - Sendai, Japan
Duration: 17 Dec 200719 Dec 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4835 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Symposium on Algorithms and Computation, ISAAC 2007
Country/TerritoryJapan
CitySendai
Period17/12/0719/12/07

Fingerprint

Dive into the research topics of 'Capacitated domination problem'. Together they form a unique fingerprint.

Cite this