On the connected domination number of random regular graphs

William Duckworth; Bernard Mans

doi:10.1007/3-540-45655-4_24

On the connected domination number of random regular graphs

William Duckworth, Bernard Mans

School of Computing

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

2 Citations (Scopus)

Abstract

A connected dominating set (CDS) of a graph, G, is a set of vertices, C ⊆ V (G), such that every vertex in V (G) \ C is incident to at least one vertex of C in G and the subgraph induced by the vertices of C in G is connected. In this paper we consider a simple, yet efficient, randomised greedy algorithm for finding a small CDS of regular graphs. We analyse the average-case performance of this heuristic on random regular graphs using differential equations. In this way we prove an upper bound on the size of a minimum CDS of random regular graphs.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings
Editors	Oscar H. Ibarra, Louxin Zhang
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	210-219
Number of pages	10
Volume	2387
ISBN (Electronic)	9783540456551
ISBN (Print)	354043996X, 9783540439967
DOIs	https://doi.org/10.1007/3-540-45655-4_24
Publication status	Published - 2002
Event	8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore Duration: 15 Aug 2002 → 17 Aug 2002

Publication series

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

Other

Other	8th Annual International Conference on Computing and Combinatorics, COCOON 2002
Country/Territory	Singapore
City	Singapore
Period	15/08/02 → 17/08/02

Access to Document

10.1007/3-540-45655-4_24

Cite this

Duckworth, W., & Mans, B. (2002). On the connected domination number of random regular graphs. In O. H. Ibarra, & L. Zhang (Eds.), Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings (Vol. 2387, pp. 210-219). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2387). Springer, Springer Nature. https://doi.org/10.1007/3-540-45655-4_24

Duckworth, William ; Mans, Bernard. / On the connected domination number of random regular graphs. Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings. editor / Oscar H. Ibarra ; Louxin Zhang. Vol. 2387 Berlin : Springer, Springer Nature, 2002. pp. 210-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{062fe293e46e4f20b1f79cbbf8183f3a,

title = "On the connected domination number of random regular graphs",

abstract = "A connected dominating set (CDS) of a graph, G, is a set of vertices, C ⊆ V (G), such that every vertex in V (G) \ C is incident to at least one vertex of C in G and the subgraph induced by the vertices of C in G is connected. In this paper we consider a simple, yet efficient, randomised greedy algorithm for finding a small CDS of regular graphs. We analyse the average-case performance of this heuristic on random regular graphs using differential equations. In this way we prove an upper bound on the size of a minimum CDS of random regular graphs.",

author = "William Duckworth and Bernard Mans",

year = "2002",

doi = "10.1007/3-540-45655-4_24",

language = "English",

isbn = "354043996X",

volume = "2387",

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

publisher = "Springer, Springer Nature",

pages = "210--219",

editor = "Ibarra, {Oscar H. } and Louxin Zhang",

booktitle = "Computing and Combinatorics",

address = "United States",

note = "8th Annual International Conference on Computing and Combinatorics, COCOON 2002 ; Conference date: 15-08-2002 Through 17-08-2002",

}

Duckworth, W & Mans, B 2002, On the connected domination number of random regular graphs. in OH Ibarra & L Zhang (eds), Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings. vol. 2387, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2387, Springer, Springer Nature, Berlin, pp. 210-219, 8th Annual International Conference on Computing and Combinatorics, COCOON 2002, Singapore, Singapore, 15/08/02. https://doi.org/10.1007/3-540-45655-4_24

On the connected domination number of random regular graphs. / Duckworth, William; Mans, Bernard.
Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings. ed. / Oscar H. Ibarra; Louxin Zhang. Vol. 2387 Berlin: Springer, Springer Nature, 2002. p. 210-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2387).

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

TY - GEN

T1 - On the connected domination number of random regular graphs

AU - Duckworth, William

AU - Mans, Bernard

PY - 2002

Y1 - 2002

N2 - A connected dominating set (CDS) of a graph, G, is a set of vertices, C ⊆ V (G), such that every vertex in V (G) \ C is incident to at least one vertex of C in G and the subgraph induced by the vertices of C in G is connected. In this paper we consider a simple, yet efficient, randomised greedy algorithm for finding a small CDS of regular graphs. We analyse the average-case performance of this heuristic on random regular graphs using differential equations. In this way we prove an upper bound on the size of a minimum CDS of random regular graphs.

AB - A connected dominating set (CDS) of a graph, G, is a set of vertices, C ⊆ V (G), such that every vertex in V (G) \ C is incident to at least one vertex of C in G and the subgraph induced by the vertices of C in G is connected. In this paper we consider a simple, yet efficient, randomised greedy algorithm for finding a small CDS of regular graphs. We analyse the average-case performance of this heuristic on random regular graphs using differential equations. In this way we prove an upper bound on the size of a minimum CDS of random regular graphs.

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

U2 - 10.1007/3-540-45655-4_24

DO - 10.1007/3-540-45655-4_24

M3 - Conference proceeding contribution

AN - SCOPUS:84892795895

SN - 354043996X

SN - 9783540439967

VL - 2387

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

SP - 210

EP - 219

BT - Computing and Combinatorics

A2 - Ibarra, Oscar H.

A2 - Zhang, Louxin

PB - Springer, Springer Nature

CY - Berlin

T2 - 8th Annual International Conference on Computing and Combinatorics, COCOON 2002

Y2 - 15 August 2002 through 17 August 2002

ER -

Duckworth W, Mans B. On the connected domination number of random regular graphs. In Ibarra OH, Zhang L, editors, Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings. Vol. 2387. Berlin: Springer, Springer Nature. 2002. p. 210-219. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45655-4_24

On the connected domination number of random regular graphs

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this