Small k-dominating sets of regular graphs

William Duckworth; Bernard Mans

doi:10.1007/3-540-45726-7_11

Small k-dominating sets of regular graphs

William Duckworth, Bernard Mans

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-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 language	English
Title of host publication	Randomization and Approximation Techniques in Computer Science
Subtitle of host publication	6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings
Editors	Jose D. P. Rolim, Salil Vadhan
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	126-138
Number of pages	13
Volume	2483
ISBN (Electronic)	9783540457268
ISBN (Print)	3540441476, 9783540441472
DOIs	https://doi.org/10.1007/3-540-45726-7_11
Publication status	Published - 2002
Event	6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002 - Cambridge, United States Duration: 13 Sept 2002 → 15 Sept 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2483
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002
Country/Territory	United States
City	Cambridge
Period	13/09/02 → 15/09/02

Access to Document

10.1007/3-540-45726-7_11

Cite this

Duckworth, W., & Mans, B. (2002). Small k-dominating sets of regular graphs. In J. D. P. Rolim, & S. Vadhan (Eds.), Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings (Vol. 2483, pp. 126-138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2483). Springer, Springer Nature. https://doi.org/10.1007/3-540-45726-7_11

Duckworth, William ; Mans, Bernard. / Small k-dominating sets of regular graphs. Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings. editor / Jose D. P. Rolim ; Salil Vadhan. Vol. 2483 Berlin : Springer, Springer Nature, 2002. pp. 126-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{48c977b1444040529e6a9c2af72a3071,

title = "Small k-dominating sets of regular graphs",

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.",

author = "William Duckworth and Bernard Mans",

year = "2002",

doi = "10.1007/3-540-45726-7_11",

language = "English",

isbn = "3540441476",

volume = "2483",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "126--138",

editor = "Rolim, {Jose D. P.} and Salil Vadhan",

booktitle = "Randomization and Approximation Techniques in Computer Science",

address = "United States",

note = "6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002 ; Conference date: 13-09-2002 Through 15-09-2002",

}

Duckworth, W & Mans, B 2002, Small k-dominating sets of regular graphs. in JDP Rolim & S Vadhan (eds), Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings. vol. 2483, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2483, Springer, Springer Nature, Berlin, pp. 126-138, 6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002, Cambridge, United States, 13/09/02. https://doi.org/10.1007/3-540-45726-7_11

Small k-dominating sets of regular graphs. / Duckworth, William; Mans, Bernard.
Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings. ed. / Jose D. P. Rolim; Salil Vadhan. Vol. 2483 Berlin: Springer, Springer Nature, 2002. p. 126-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2483).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

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 -

Duckworth W, Mans B. Small k-dominating sets of regular graphs. In Rolim JDP, Vadhan S, editors, Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings. Vol. 2483. Berlin: Springer, Springer Nature. 2002. p. 126-138. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45726-7_11

Small k-dominating sets of regular graphs

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this