2016/08/27 by Zhang, Zhao, Zhou, Jiao, Huang, Xiaohui +1
#05C85 #68W25 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.1608.07634
To achieve an efficient routing in a wireless sensor network, connected dominating set (CDS) is used as virtual backbone. A fault-tolerant virtual backbone can be modeled as a (k,m)-CDS. For a connected graph G=(V,E) and two fixed integers k and m, a node set C⊆ V is a (k,m)-CDS of G if every node in V∖ C has at least m neighbors in C, and the subgraph of G induced by C is k-connected. Previous to this work, approximation algorithms with guaranteed performance ratio in a general graph were know only for k≤ 3. This paper makes a significant progress by presenting a (2k-1)α0 approximation algorithm for general k and m with m≥ k, where α0 is the performance ratio for the minimum CDS problem. Using currently best known ratio for α0, our algorithm has performance ratio O(lnΔ), where Δ is the maximum degree of the graph.