Carnegie Mellon University
Browse
file.pdf (372.27 kB)

On the length of a random minimum spanning tree

Download (372.27 kB)
journal contribution
posted on 2013-03-09, 00:00 authored by Colin Cooper, Alan FriezeAlan 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

2013-03-09

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC