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 $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].

    https://doi.org/10.46298/dmtcs.3513
    Source: HAL:hal-01184718v1
    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: [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], [en] Minimum Spanning Trees, Random Graphs, Kruskal's Algorithm, Branching Processes, Ballot Theorem

    4 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 477 times.
    This article's PDF has been downloaded 401 times.