Abstract
We study the expected value of the length Ln of the minimum spanning tree of the complete graph Kn when each edge e is given an independent uniform [0, 1] edge weight. We sharpen the result of Frieze [6] that lim n→â (Ln) = ζ(3) and show that where c 1, c 2 are explicitly defined constants.
Original language | English (US) |
---|---|
Pages (from-to) | 89-107 |
Number of pages | 19 |
Journal | Combinatorics Probability and Computing |
Volume | 25 |
Issue number | 1 |
DOIs | |
State | Published - Jan 1 2016 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics