Geodesic
A note on random minimum length spanning trees
The electronic journal of combinatorics, Tome 7 (2000)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Consider a connected $r$-regular $n$-vertex graph $G$ with random independent edge lengths, each uniformly distributed on $[0,1]$. Let $mst(G)$ be the expected length of a minimum spanning tree. We show in this paper that if $G$ is sufficiently highly edge connected then the expected length of a minimum spanning tree is $\sim {n\over r}\zeta(3)$. If we omit the edge connectivity condition, then it is at most $\sim {n\over r}(\zeta(3)+1)$.
DOI : 10.37236/1519
Classification : 05C80, 05C05
Mots-clés : random edge lengths, spanning tree 
@article{10_37236_1519,
     author = {Alan Frieze and Mikl\'os Ruszink\'o and Lubos Thoma},
     title = {A note on random minimum length spanning trees},
     journal = {The electronic journal of combinatorics},
     year = {2000},
     volume = {7},
     doi = {10.37236/1519},
     zbl = {0958.05123},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1519/}
}
TY  - JOUR
AU  - Alan Frieze
AU  - Miklós Ruszinkó
AU  - Lubos Thoma
TI  - A note on random minimum length spanning trees
JO  - The electronic journal of combinatorics
PY  - 2000
VL  - 7
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1519/
DO  - 10.37236/1519
ID  - 10_37236_1519
ER  - 
%0 Journal Article
%A Alan Frieze
%A Miklós Ruszinkó
%A Lubos Thoma
%T A note on random minimum length spanning trees
%J The electronic journal of combinatorics
%D 2000
%V 7
%U http://geodesic.mathdoc.fr/articles/10.37236/1519/
%R 10.37236/1519
%F 10_37236_1519
Alan Frieze; Miklós Ruszinkó; Lubos Thoma. A note on random minimum length spanning trees. The electronic journal of combinatorics, Tome 7 (2000). doi: 10.37236/1519

Cité par Sources :