file.pdf (372.27 kB)

On the length of a random minimum spanning tree

Download (372.27 kB)
journal contribution
posted on 09.03.2013, 00:00 by Colin Cooper, Alan Frieze, Nate Ince, Svante Janson, Joel Spencer

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 \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.




Usage metrics