TY - GEN

T1 - Small k-dominating sets of regular graphs

AU - Duckworth, William

AU - Mans, Bernard

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84959042817&partnerID=8YFLogxK

U2 - 10.1007/3-540-45726-7_11

DO - 10.1007/3-540-45726-7_11

M3 - Conference proceeding contribution

AN - SCOPUS:84959042817

SN - 3540441476

SN - 9783540441472

VL - 2483

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 126

EP - 138

BT - Randomization and Approximation Techniques in Computer Science

A2 - Rolim, Jose D. P.

A2 - Vadhan, Salil

PB - Springer, Springer Nature

CY - Berlin

T2 - 6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002

Y2 - 13 September 2002 through 15 September 2002

ER -