## 6 Clustering, Virtual Backbone and Minimum Connected Dominating Set
### Constructive Algorithms  
[PERSON] and [PERSON]'s seminal paper [89] shows that a \(\beta\) approximation for the problem of finding the MCDS corresponds to a \(2\beta\) approximation for another NP-hard problem, the travelling tourist problem. It uses this result as the basis for two polynomial time approximation algorithms for the MCDS problem. Figure 2: An example of Minimum Connected Dominating Set. These two algorithms have approximation factors of \(2(H(\Delta)+1)\) and \(H(\Delta)+2\), respectively, in which \(\Delta\) is the maximum nodal degree and \(H\) is the harmonic function [90]. The first algorithm approximates the MCDS by greedily creating a tree \(T\). All the non-leaf nodes of \(T\) form the approximate MCDS, which is indeed a CDS. Nodes have three different states, which are black, grey and white. Black nodes are nodes in the final CDS, so called dominators. Grey nodes are candidates of dominators, and white nodes are those nodes not yet in \(T\). Initially, all the nodes are white nodes, and the algorithm finds out the node with maximum degree of white neighbors, marks it black, and marks all its white neighbors grey. The algorithm then iteratively marks the grey node or the pair of connected grey nodes that have maximum white neighbors to black, and update those white neighbors to grey state. The set of black nodes in the final result is the CDS. Note the correspondence of grey and black nodes to candidate and confirmed nodes in [PERSON]'s algorithm [91]; however a notable difference between the algorithms is that the order of processing the grey nodes is based on their connectivity rather than the cost of the path. To develop the second algorithm, [PERSON] and [PERSON] introduced a new concept called _piece_, defined as either a connected black component, or a white node. The second algorithm selects nodes with maximum degree of _pieces_ as dominators until there are no white nodes. It then connects all the dominators by constructing a Steiner tree. A distributed algorithm is called _localized_ if each node decides on its own behavior based on only the information from nodes within a limited hop distance, e.g., one or two hops. With localized algorithms, topology changes in part of the network can be isolated, and may not affect the rest of the network. In contrast, a distributed non-localized algorithm requires nodes to acquire global knowledge of the network to perform correct operations [92]. Neither of the above algorithms is localized, as they need global information to select the nodes with maximum degree of white neighbors or _pieces_. [PERSON] and [PERSON] [93] proposed to construct a virtual backbone in a wireless ad hoc network by using its MCDS, and developed a distributed implementation of [PERSON] and [PERSON]'s algorithm. [PERSON] and [PERSON]'s distributed algorithm is also non-localized, as the centralized algorithm it is based on finds a non-localized solution. Another distributed heuristic to compute the MCDS for a wireless ad hoc network was proposed by [PERSON] and [PERSON] [94]. The algorithm is non-localized as it involves the construction of a spanning tree. Indeed, this algorithm follows the same idea as the second algorithm of [PERSON] and [PERSON]. It selects a dominating set first, and then connects nodes in the dominating set by choosing some additional nodes as connectors. The selection of the dominating set is based on the construction of a maximal independent set (MIS), and the connection step is completed by selecting some additional nodes to form a spanning tree. The authors provided performance bounds by applying the property that a node in a unit disk graph cannot have more than five independent neighbors [95]. If \(n\) is the number of vertices for the whole network, the algorithm has time complexity of \(O(n)\), and message complexity of \(O(n\log(n))\), while providing a constant approximation factor. This algorithm is non-localized as it needs a leader node to generate a rooted tree.