Capacitated Domination Problem
Date Issued
2008
Date
2008
Author(s)
Kao, Mong-Jen
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 is met by the capacities of vertices in D dominating it.n this thesis, 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 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.
Subjects
algorithm
graph theory
domination
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922078-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):04fb9ad3d8edf2233b1ab73b06f5acdb