Capacitated Domination: Constant Factor Approximation for Planar Graphs

Details Capacitated Domination: Constant Factor Approximation for Planar Graphs Capacitated Domination: Constant Factor Approximation for Planar Graphs

2011-08-23

arxiv.org/abs/1108.4606v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this problem, we are given a graph with three parameters defined on the vertex set, which are cost, capacity, and demand. The objective of this problem is to compute a demand assignment of least cost, such that the demand of each vertex is fully-assigned to some of its closed neighbours without exceeding the amount of capacity they provide. In this paper, we provide the first constant factor approximation for this problem on planar graphs, based on a new perspective on the hierarchical structure of outer-planar graphs. We believe that this new perspective and technique can be applied to other capacitated covering problems to help tackle vertices of large degrees.

Affiliated with

Also associated with

No associations

Rating

Capacitated Domination: Constant Factor Approximation for Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Capacitated Domination: Constant Factor Approximation for Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capacitated Domination: Constant Factor Approximation for Planar Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67332