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

Abstract

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 <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-connected <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>-dominating set (abbreviated as a <inline-formula> <tex-math notation="LaTeX">$(k,m)$ </tex-math></inline-formula>-CDS) in a graph. In this paper, we present an approximation algorithm for the minimum weight <inline-formula> <tex-math notation="LaTeX">$(2,m)$ </tex-math></inline-formula>-CDS problem in a general graph, which achieves approximation ratio at most <inline-formula> <tex-math notation="LaTeX">$5.164H(n-1)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$H(\gamma)=\sum _{i=1}^{\gamma }1/i$ </tex-math></inline-formula> is the <inline-formula> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>th Harmonic number and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the number of nodes in the graph. This ratio improves previously best known ratio by a factor of at least 3.87.