Metaheuristics For Ad Hoc Network Clustering: A Graph-Theoretic Perspective - Ho, Chin Kuan (2007)
The ant colony optimization (ACO) metaheuristic has been successfully applied to two computationally difficult graph-theoretic problems arising from the task of clustering nodes in ad hoc networks. In such clustering, each node is either a cluster head (CH) or an ordinary node attached to a CH. The construction of the minimum number of clusters is formulated as the Minimum Dominating Set (MDS) problem, which is known to be NP-Hard and computationally intractable.