A weakly-connected dominating set, W, of a graph, G, is a dominating set such that the subgraph consisting of V(G) and all edges incident with vertices in W is connected. Finding a small weakly-connected dominating set of a graph has important applications in clustering mobile ad-hoc networks. In this paper we introduce several new randomised greedy algorithms for finding small weakly-connected dominating sets of regular graphs. These heuristics proceed by growing a weakly-connected dominating set in the graph. We analyse the average-case performance of the simplest such heuristic on random regular graphs using differential equations. This introduces upper bounds on the size of a smallest weakly-connected dominating set of a random regular graph. We then show that for random regular graphs, other "growing" greedy strategies have exactly the same average-case performance as the simple heuristic.
|Number of pages||13|
|Journal||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Publication status||Published - 2003|
- Dominating sets
- Random regular graphs