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 subset of V is a (k, m)-CDS of G if every node in VC 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)alpha(0) approximation algorithm for general k and m with m = k, where alpha(0) is the performance ratio for the minimum (1, m)-CDS problem. Using a currently best-known ratio for alpha(0), our algorithm has performance ratio O(ln Delta), where Delta is the maximum degree of the graph. Simulation results validate the effectiveness of our algorithm.