file.pdf (372.27 kB)
0/0

On the length of a random minimum spanning tree

Download (372.27 kB)
journal contribution
posted on 09.03.2013 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.

History

Date

09/03/2013

Exports

Exports