Performance Guaranteed Approximation Algorithm for Minimum $k$-Connected $m$-Fold Dominating Set

Zhao Zhang, Jiao Zhou, Xiaohui Huang +1

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,…