Computing Minimum k-Connected m-Fold Dominating Set in General Graphs

Connected dominating set (CDS) problem has been extensively studied in the literature due to its applications in many domains, including computer science and operations research. For example, CDS has been recommended to serve as a virtual backbone in wireless sensor networks (WSNs). Since sensor nodes in WSNs are prone to failures, it is important to build a fault-tolerant virtual backbone that maintains a certain degree of redundancy. A fault-tolerant virtual backbone can be modeled as a k-connected m-fold dominating set (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 known only for k ≤ 3. This paper makes significant progress by presenting a (2k − 1)α₀ approximation algorithm for general k and m with m ≥ k, where α₀ is the performance ratio for the minimum (1, m)-CDS problem. Using a currently best-known ratio for α₀, our algorithm has performance ratio O(lnΔ), where Δ is the maximum degree of the graph. Simulation results validate the effectiveness of our algorithm.