Geodesic
Minimum connected dominating sets of random cubic graphs
The electronic journal of combinatorics, Tome 9 (2002)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$.
DOI : 10.37236/1624
Classification : 05C80, 05C69
Mots-clés : random graph, cubic graphs, connected dominating set 
@article{10_37236_1624,
     author = {W. Duckworth},
     title = {Minimum connected dominating sets of random cubic graphs},
     journal = {The electronic journal of combinatorics},
     year = {2002},
     volume = {9},
     doi = {10.37236/1624},
     zbl = {0986.05089},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1624/}
}
TY  - JOUR
AU  - W. Duckworth
TI  - Minimum connected dominating sets of random cubic graphs
JO  - The electronic journal of combinatorics
PY  - 2002
VL  - 9
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1624/
DO  - 10.37236/1624
ID  - 10_37236_1624
ER  - 
%0 Journal Article
%A W. Duckworth
%T Minimum connected dominating sets of random cubic graphs
%J The electronic journal of combinatorics
%D 2002
%V 9
%U http://geodesic.mathdoc.fr/articles/10.37236/1624/
%R 10.37236/1624
%F 10_37236_1624
W. Duckworth. Minimum connected dominating sets of random cubic graphs. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1624

Cité par Sources :