The Diameter of the Minimum Spanning Tree of a Complete Graph

Abstract : 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].
Keywords :
Document type :
Conference papers
Domain :

Cited literature [18 references]

https://hal.inria.fr/hal-01184718
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 2:25:43 PM
Last modification on : Thursday, February 7, 2019 - 4:56:57 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:11:30 PM

File

dmAG0116.pdf
Publisher files allowed on an open archive

Identifiers

• HAL Id : hal-01184718, version 1

Citation

Louigi Addario-Berry, Nicolas Broutin, Bruce Reed. The Diameter of the Minimum Spanning Tree of a Complete Graph. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.237-248. ⟨hal-01184718⟩

Record views