Given an undirected graph on a node set V and positive integers k and m, a k-connected m-dominating set ((k, m)-CDS) is defined as a subset S of V such that each node in has at least m neighbors in S, and a k-connected subgraph is induced by S. The weighted (k, m)-CDS problem is to find a minimum weight (k, m)-CDS in a given node-weighted graph. The problem is called the unweighted (k, m)-CDS problem if the objective is to minimize the cardinality of a (k, m)-CDS. These problems have been actively studied for unit disk graphs, motivated by the application of constructing a virtual backbone in a wireless ad hoc network. In this paper, we consider the case in which , and we present a simple -approximation algorithm for the unweighted (k, m)-CDS problem, and a primal-dual -approximation algorithm for the weighted (k, m)-CDS problem.
展开▼
