Minimum connected dominating sets of random cubic graphs (Q5958835): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 01:23, 30 January 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
