On the Length of a Random Minimum Spanning Tree
- 23 January 2015
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 25 (1) , 89-107
Abstract
We study the expected value of the lengthLnof the minimum spanning tree of the complete graphKnwhen each edgeeis given an independent uniform [0, 1] edge weight. We sharpen the result of Frieze [6] that limn→∞ $\mathbb{E}$ (Ln) = ζ(3) and show that $$ \mathbb{E}(L_n)=\zeta(3)+\frac{c_1}{n}+\frac{c_2+o(1)}{n^{4/3}}, $$ wherec1,c2are explicitly defined constants.
Keywords
All Related Versions
This publication has 1 reference indexed in Scilit: