Minimum connected dominating sets of random cubic graphs (Q5958835): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Latest revision as of 23:49, 4 March 2024
scientific article; zbMATH DE number 1716038
| Language | Label | Description | Also known as |
|---|---|---|---|
| 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
