Louigi Addario-Berry ; Nicolas Broutin ; Bruce Reed - The Diameter of the Minimum Spanning Tree of a Complete Graph

dmtcs:3513 - Discrete Mathematics & Theoretical Computer Science, January 1, 2006, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities - https://doi.org/10.46298/dmtcs.3513
The Diameter of the Minimum Spanning Tree of a Complete GraphConference paper

Authors: Louigi Addario-Berry ; Nicolas Broutin ; Bruce Reed

    Let X1,,X(n2) be independent identically distributed weights for the edges of Kn. If XiXj forij, 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].


    Volume: DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
    Section: Proceedings
    Published on: January 1, 2006
    Imported on: May 10, 2017
    Keywords: Minimum Spanning Trees,Random Graphs,Kruskal's Algorithm,Branching Processes,Ballot Theorem,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

    4 Documents citing this article

    Consultation statistics

    This page has been seen 285 times.
    This article's PDF has been downloaded 275 times.