Randomised algorithms for finding small weakly-connected dominating sets of regular graphs

William Duckworth*, Bernard Mans

*Corresponding author for this work

Research output: Contribution to journalArticle

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)83-95
Number of pages13
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2653
Publication statusPublished - 2003

Keywords

  • Dominating sets
  • Random regular graphs
  • Weakly-connected

Fingerprint Dive into the research topics of 'Randomised algorithms for finding small weakly-connected dominating sets of regular graphs'. Together they form a unique fingerprint.

Cite this