Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The Diameter of the ...
Conference paper

The Diameter of the Minimum Spanning Tree of a Complete Graph

Louigi Addario-Berry, Nicolas Broutin, Bruce Reed
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2005
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Proceedings
DOI
10.46298/dmtcs.3513
License
https://about.hal.science/hal-authorisation-v1
Indicators
1002
Views
628
Downloads

The Diameter of the Minimum Spanning Tree of a Complete Graph

Louigi Addario-Berry, Nicolas Broutin, Bruce Reed
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
  • [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]
  • Minimum Spanning Trees
  • Random Graphs
  • Kruskal's Algorithm
  • Branching Processes
  • Ballot Theorem
Cited by

Source: OpenCitations

  • Weak disorder asymptotics in the stochastic mean-field model of distance

    arXiv (Cornell University)

    Authors : Shankar Bhamidi, Remco van der Hofstad

    Journal reference : Volume 22, 2012, pp.

    DOI : 10.1214/10-aap753

  • Depth functions and mutidimensional medians on minimal spanning trees

    PubMed Central

    Authors : Mengta Yang, Reza Modarres ORCID, Lingzhe Guo

    Journal reference : Volume 47, 2019, pp. 323-336

    DOI : 10.1080/02664763.2019.1636939

  • Average Update Times for Fully-Dynamic All-Pairs Shortest Paths

    Lecture notes in computer science

    Authors : Tobias Friedrich ORCID, Nils Hebbinghaus

    Journal reference : Volume , 2008, pp. 692-703

    DOI : 10.1007/978-3-540-92182-0_61

  • The continuum limit of critical random graphs

    Probability Theory and Related Fields

    Authors : L. Addario-Berry ORCID, N. Broutin, C. Goldschmidt ORCID

    Journal reference : Volume 152, 2010, pp. 367-406

    DOI : 10.1007/s00440-010-0325-4
Preview
Loading PDF preview...