Connected dominating sets are one of the primary techniques used to build backbones for wireless sensor and *ad hoc* networks. The concept of CDS can be briefly introduced as follows. A dominating set (DS) is a subset of the vertices of a graph where every vertex in the graph is either in the subset or is adjacent to at least one vertex in the subset. A CDS is a connected DS. The nodes in CDS are called *dominators*, while other nodes are called *dominatees*. There are several metrics used to evaluate the quality of a backbone protocol. They evaluate its properties such as backbone size, protocol duration, message overhead and backbone robustness (Basagni *et al*., 2006). It is normally desirable to construct a backbone with the smallest size possible and thus prolong the lifetime of the network and alleviate congestion. That is, it is useful to find the minimum connected dominating set (MCDS). However, finding the MCDS in general graphs has been shown to be equivalent to the set cover problem which is NP-hard (Garey and Johnson, 1978). The MCDS remains NP-hard even in UDGs (Clark *et al.*, 1990). Therefore, approximation algorithms and heuristic algorithms have been proposed in literature to solve the problem. Approximation algorithms are normally evaluated by the *approximation/performance ratio*, which is upper bound on the ratio of the algorithm's performance to the optimal algorithm's performance. Algorithms introduced next can be classified ...

Start Free Trial

No credit card required