Randomized greedy algorithms for finding small k-dominating sets of regular graphs

W. Duckworth*, B. Mans

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

A k-dominating set of a graph G is a subset D of the vertices of G such that every vertex of G is either in D or at distance at most k from a vertex in D. It is of interest to find k-dominating sets of small cardinality. In this paper we consider simple randomized greedy algorithms for finding small k-dominating sets of regular graphs. We analyze the average-case performance of the most efficient of these simple heuristics showing that it performs surprisingly well on average. The analysis is performed on random regular graphs using differential equations. This, in turn, proves upper bounds on the size of a minimum k-dominating set of random regular graphs.

Original languageEnglish
Pages (from-to)401-412
Number of pages12
JournalRandom Structures and Algorithms
Volume27
Issue number3
DOIs
Publication statusPublished - Oct 2005

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

Cite this