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 Graph

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: 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

    Share and export

    Consultation statistics

    This page has been seen 148 times.
    This article's PDF has been downloaded 156 times.