## 6 Clustering, Virtual Backbone and Minimum Connected Dominating Set
### Cluster Routing Protocols
Unfortunately, finding an MCDS in a given connected graph is not as easy in practical situations as in the previous example. This problem is known to be NP-hard [87]. Some papers study properties of the MCDS directly, such as [PERSON] _et al._[88], which evaluated the cardinality of the MCDS probabilistically for random networks. However, research activity on MCDS problem mainly focuses on providing heuristics or approximation algorithms, which achieve near MCDS construction. Note the difference between heuristics and approximation algorithms. An algorithm \(A\) is called a \(\alpha\)-approximation if it can be proved that \(A\) will not be more than a factor \(\alpha\) times the optimum solution \(s_{opt}\), i.e., \(A\leq\alpha s_{opt}\). The \(\alpha\) is called the approximation ratio of \(A\). In contrast, a heuristic is any algorithm which appears to work well in most cases. Existing algorithms for constructing an approximate MCDS can be classified into three categories: constructive, pruning-based and multipoint-relay-based algorithms. Constructive algorithms approximate the MCDS in a graph by gradually adding nodes to a candidate set. In contrast, pruning-basedalgorithms begin with taking a large candidate set, then detect and remove redundant nodes to eventually obtain a small CDS. The last type, multipoint-relay-based algorithms, allows each node to determine its smallest one-hop message relay set, and all nodes selected as relay nodes for a particular message relaying form a CDS. For all three types of algorithms, the connectivity among the relay nodes must be considered. A common approach used by constructive algorithms is first to select a subset of a CDS, called a **M**aximal Independent Set (MIS), and then using some additional nodes to provide connectivity among nodes in the MIS. Algorithms in this class are generally differentiated according to the approaches used to produce the MIS and to find the additional nodes. An independent set (IS) of a graph \(G=(V,E)\) is defined as a subset \(\overline{V}\subseteq V\), such that there is no edge between any two vertices in \(\overline{V}\), i.e., \(\forall\ u,v\in\overline{V}\), \((u,v)\
otin E\). An independent set that is not a proper subset of any other independent set is called a maximal independent set. Note the difference between a max_imal_ independent set and a max_imum_ independent set. The latter is defined as an independent set with the largest cardinality, but there can be multiple maximal independent sets with varying cardinality. While construction of a maximal independent set can be solved in polynomial time by greedy algorithms, finding the maximum independent sets is NP-complete [87]. In contrast to constructive algorithms, pruning-based algorithms generate a large CDS first, and then remove redundant nodes while keeping the connectivity among the remaining nodes in the CDS. In terms of the multipoint-relay-based algorithms, the connectivity of the constructed dominating set is guaranteed in the selection of multipoint relay nodes. These three types of algorithms are described in more detail in the following subsections. Typical examples of each type are also discussed.