file.pdf (372.27 kB)
On the length of a random minimum spanning tree
journal contribution
posted on 2013-03-09, 00:00 authored by Colin Cooper, Alan FriezeAlan Frieze, Nate Ince, Svante Janson, Joel SpencerWe 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 \cite{F1} that $\lim_{n\to\infty}\E(L_n)=\z(3)$ and show that$\E(L_n)=\z(3)+\frac{c_1}{n}+\frac{c_2+o(1)}{n^{4/3}}$ where c1,c2 are explicitly defined constants.