A New Approximation Algorithm for Minimum-Weight (1, m)–Connected Dominating Set

Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least m neighbors in the subset, then the node subset is called a (1, m)CDS. The minimumweight (1, m)CDS problem aims at finding a (1, m)CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem, which improves previous ratio by a factor of 2/3.