Geodesic
The Diameter of the Minimum Spanning Tree of a Complete Graph
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006).

Voir la notice de l'article provenant de la source Episciences

Let $X_1,\ldots,X_{n\choose 2}$ be independent identically distributed weights for the edges of $K_n$. If $X_i \neq X_j$ for$ i \neq j$, then there exists a unique minimum weight spanning tree $T$ of $K_n$ with these edge weights. We show that the expected diameter of $T$ is $Θ (n^{1/3})$. This settles a question of [Frieze97]. 
@article{DMTCS_2006_special_252_a37,
     author = {Addario-Berry, Louigi and Broutin, Nicolas and Reed, Bruce},
     title = {The {Diameter} of the {Minimum} {Spanning} {Tree} of a {Complete} {Graph}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities},
     year = {2006},
     doi = {10.46298/dmtcs.3513},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3513/}
}
TY  - JOUR
AU  - Addario-Berry, Louigi
AU  - Broutin, Nicolas
AU  - Reed, Bruce
TI  - The Diameter of the Minimum Spanning Tree of a Complete Graph
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3513/
DO  - 10.46298/dmtcs.3513
LA  - en
ID  - DMTCS_2006_special_252_a37
ER  - 
%0 Journal Article
%A Addario-Berry, Louigi
%A Broutin, Nicolas
%A Reed, Bruce
%T The Diameter of the Minimum Spanning Tree of a Complete Graph
%J Discrete mathematics & theoretical computer science
%D 2006
%V DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3513/
%R 10.46298/dmtcs.3513
%G en
%F DMTCS_2006_special_252_a37
Addario-Berry, Louigi; Broutin, Nicolas; Reed, Bruce. The Diameter of the Minimum Spanning Tree of a Complete Graph. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006). doi : 10.46298/dmtcs.3513. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3513/

Cité par Sources :