Carnegie Mellon University
Browse
file.pdf (422.33 kB)

On edge disjoint spanning trees in a randomly weighted complete graph

Download (422.33 kB)
journal contribution
posted on 2015-05-13, 00:00 authored by Alan FriezeAlan Frieze, Tony Johansson

Assume that the edges of the complete graph Kn are given independent uniform [0,1] edges weights. We consider the expected minimum total weight μk of k≥2 edge disjoint spanning trees. When k is large we show that μk≈k2. Most of the paper is concerned with the case k=2. We show that $\m_2$ tends to an explicitly defined constant and that μ2≈4.1704288….

History

Date

2015-05-13

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC