Small k-dominating sets of regular graphs

William Duckworth, Bernard Mans

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

1 Citation (Scopus)

Abstract

A k-dominating set of a graph, G, is a set of vertices, D ⊆ V (G), such that for every vertex v ∈ V (G), either v ∈ D or there exists a vertex u ∈ D that is at distance at most k from v in G. We are interested in finding k-dominating sets of small cardinality. In this paper we consider a simple, yet efficient, randomised greedy algorithm for finding a small k-dominating set of regular graphs. We analyse the average-case performance of this heuristic by analysing its performance on random regular graphs using differential equations. This, in turn, proves an upper bound on the size of a minimum k-dominating set of random regular graphs.

Original languageEnglish
Title of host publicationRandomization and Approximation Techniques in Computer Science
Subtitle of host publication6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings
EditorsJose D. P. Rolim, Salil Vadhan
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages126-138
Number of pages13
Volume2483
ISBN (Electronic)9783540457268
ISBN (Print)3540441476, 9783540441472
DOIs
Publication statusPublished - 2002
Event6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002 - Cambridge, United States
Duration: 13 Sep 200215 Sep 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2483
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002
CountryUnited States
CityCambridge
Period13/09/0215/09/02

Fingerprint Dive into the research topics of 'Small k-dominating sets of regular graphs'. Together they form a unique fingerprint.

Cite this