DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

The Diameter of the Minimum Spanning Tree of a Complete Graph

Louigi Addario-Berry, Nicolas Broutin, Bruce Reed

Abstract


Let {X1,…,Xn&choose;2} be independent identically distributed weights for the edges of Kn. If Xi ≠Xj for i ≠j, then there exists a unique minimum weight spanning tree T of Kn with these edge weights. We show that the expected diameter of T is Θ(n1/3). This settles a question of [Frieze97].

Full Text: PDF

Valid XHTML 1.0 Transitional