## 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 language | English |
---|---|

Pages (from-to) | 401-412 |

Number of pages | 12 |

Journal | Random Structures and Algorithms |

Volume | 27 |

Issue number | 3 |

DOIs | |

Publication status | Published - Oct 2005 |