Premium
Randomized greedy algorithms for finding small k ‐dominating sets of regular graphs
Author(s) -
Duckworth W.,
Mans B.
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20082
Subject(s) - greedy algorithm , greedy randomized adaptive search procedure , computer science , algorithm , dominating set , combinatorics , mathematics , theoretical computer science , graph , vertex (graph theory)
A k ‐dominating set of a graph G is a subset of the vertices of G such that every vertex of G is either in or at distance at most k from a vertex in . 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. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 22, 2005