Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks

We present a series of approximation algorithms for finding a small weakly-connected dominating set (WCDS) in a given graph to be used in clustering mobile ad hoc networks. The structure of a graph can be simplified using WCDS's and made more succinct for routing in ad hoc networks. The theoretical performance ratio of these algorithms is O(ln Δ) compared to the minimum size WCDS, where Δ is the maximum degree of the input graph. The first two...