Capacitated domination problem

Mong Jen Kao, Chung Shou Liao*, D. T. Lee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 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 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.

Original languageEnglish
Pages (from-to)274-300
Number of pages27
JournalAlgorithmica (New York)
Volume60
Issue number2
DOIs
StatePublished - Jun 2011

Keywords

  • Algorithm
  • Domination
  • Facility location

Fingerprint

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

Cite this