## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 83-95 |

Number of pages | 13 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 2653 |

Publication status | Published - 2003 |

## Keywords

- Dominating sets
- Random regular graphs
- Weakly-connected