An Efficient Centralized Algorithm for Connected Dominating Set on Wireless Networks

In wireless network, backbone network plays an important role on forwarding data. Further, in order to reduce the delay and save energy, the minimum connected dominating set (MCDS) is an effective way to construct a backbone. However, it is NP-hard to construct the MCDS. In this paper, we propose an efficient centralized algorithm, redundancy connected dominating set (RCDS), to construct a relatively optimal connected dominating set with the economic computation cost of O(Δ2n) Specifically, the local strategy is employed to obtain the maximal independent set (MIS) firstly, and then a virtual backbone network is generated by adding the local joint intermediate nodes in the general graph.