Approximation Algorithm for Minimum Weight $(2,m)$-Connected Dominating Set

Using a connected dominating set (CDS) as a virtual backbone of a wireless sensor network can effectively save energy, reduce interference, and extend network lifespan, which also has wide applications in geometric routing algorithms and network topology control. A fault-tolerant virtual backbone can be modeled as a $k$-connected $m$-dominating set (abbreviated as a $(k,m)$-CDS) in a graph. In this paper, we present an approximation algorithm for the minimum weight $(2,m)$-CDS problem in a general graph, which achieves approximation ratio at most $5.164H(n-1)$, where $H(\\gamma)=\\sum_{i=1}^{\\gamma}1\/i$ is the $\\gamma$th Harmonic number and $n$ is the number of nodes in the graph. This ratio improves previously best known ratio by a factor of at least $3.87$.