Minimum connected dominating sets of random cubic graphs (Q5958835)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1716038
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Minimum connected dominating sets of random cubic graphs |
scientific article; zbMATH DE number 1716038 |
Statements
Minimum connected dominating sets of random cubic graphs (English)
0 references
4 March 2002
0 references
Summary: We present a simple heuristic for finding a small connected dominating set of cubic graphs. The average-case performance of this heuristic, which is a randomised greedy algorithm, is analysed on random \(n\)-vertex cubic graphs using differential equations. In this way, we prove that the expected size of the connected dominating set returned by the algorithm is asymptotically almost surely less than \(0.5854n\).
0 references
random graph
0 references
cubic graphs
0 references
connected dominating set
0 references
0 references
0.95403725
0 references
0.91702735
0 references
0.91441405
0 references
0.8982191
0 references
0.8973214
0 references
