2015/10/20 by Zhao Zhang, Jiao Zhou, Zhang, Zhao +5
Computer Science · #05C85 #68W25 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #G.2.2 #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1510.05886
openalex publication_date 2015/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Using connected dominating set (CDS) to serve as a virtual backbone in a wireless networks can save energy and reduce interference. Since nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone has some fault-tolerance. A k-connected m-fold dominating set ((k,m)-CDS) of a graph G is a node set D such that every node in V∖ D has at least m neighbors in D and the subgraph of G induced by D is k-connected. Using (k,m)-CDS can tolerate the failure of min\k-1,m-1\ nodes. In this paper, we study Minimum Weight (1,m)-CDS problem ((1,m)-MWCDS), and present an (H(δ+m)+2H(δ-1))-approximation algorithm, where δ is the maximum degree of the graph and H(⋅) is the Harmonic number. Notice that there is a 1.35ln n-approximation algorithm for the (1,1)-MWCDS problem, where n is the number of nodes in the graph. Though our constant in O(ln ⋅) is larger than 1.35, n is replaced by δ. Such a replacement enables us to obtain a (6.67+ε)-approximation for the (1,m)-MWCDS problem on unit disk graphs.