CAPACITATED DOMINATION generalizes the classic DOMINATING SET problem by specifying for each vertex a required demand and an available capacity for covering demand in its closed neighborhood. The objective is to find a minimum-size set of vertices that can cover all of the graph's demand without exceeding any of the capacities. CAPACITATED r-DOMINATION further generalizes the problem by allowing vertices to cover demand up to a distance r away. In this paper we look specifically at domination problems with hard capacities (i.e. each vertex can appear at most once in the solution). Previous complexity results suggest that this problem cannot be solved (or even closely approximated) efficiently in general graphs. In this paper we present polynomial-time approximation schemes for CAPACITATED DOMINATION and CAPACITATED r-DOMINATION in unweighted planar graphs when the maximum capacity is bounded. We also show how this result can be extended to the closely-related CAPACITATED VERTEX COVER problem.
展开▼
