On the Length of a Random Minimum Spanning Tree

Colin Cooper; Alan Frieze; Nate Ince; Svante Janson; Joel Spencer

doi:10.1017/S0963548315000024

On the Length of a Random Minimum Spanning Tree

Colin Cooper, Alan Frieze, Nate Ince, Svante Janson, Joel Spencer

Research output: Contribution to journal › Article › peer-review

Abstract

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 [6] that lim n→â (Ln) = ζ(3) and show that where c 1, c 2 are explicitly defined constants.

Original language	English (US)
Pages (from-to)	89-107
Number of pages	19
Journal	Combinatorics Probability and Computing
Volume	25
Issue number	1
DOIs	https://doi.org/10.1017/S0963548315000024
State	Published - Jan 1 2016

ASJC Scopus subject areas

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548315000024

Cite this

@article{7b60639b64624813b1cb69a60942c23f,

title = "On the Length of a Random Minimum Spanning Tree",

abstract = "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 [6] that lim n→{\^a} (Ln) = ζ(3) and show that where c 1, c 2 are explicitly defined constants.",

author = "Colin Cooper and Alan Frieze and Nate Ince and Svante Janson and Joel Spencer",

note = "Funding Information: In an earlier version of this paper, we showed that E(Ln) = ζ(3) + c1 + o(1) /n . Nick Read directed us to his article [24], which suggested that the o(1/n) term could be replaced by (c + o(1))/n Publisher Copyright: {\textcopyright} 2015 Cambridge University Press.",

year = "2016",

month = jan,

day = "1",

doi = "10.1017/S0963548315000024",

language = "English (US)",

volume = "25",

pages = "89--107",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "1",

}

TY - JOUR

T1 - On the Length of a Random Minimum Spanning Tree

AU - Cooper, Colin

AU - Frieze, Alan

AU - Ince, Nate

AU - Janson, Svante

AU - Spencer, Joel

N1 - Funding Information: In an earlier version of this paper, we showed that E(Ln) = ζ(3) + c1 + o(1) /n . Nick Read directed us to his article [24], which suggested that the o(1/n) term could be replaced by (c + o(1))/n Publisher Copyright: © 2015 Cambridge University Press.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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 [6] that lim n→â (Ln) = ζ(3) and show that where c 1, c 2 are explicitly defined constants.

AB - 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 [6] that lim n→â (Ln) = ζ(3) and show that where c 1, c 2 are explicitly defined constants.

UR - http://www.scopus.com/inward/record.url?scp=84952980538&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84952980538&partnerID=8YFLogxK

U2 - 10.1017/S0963548315000024

DO - 10.1017/S0963548315000024

M3 - Article

AN - SCOPUS:84952980538

SN - 0963-5483

VL - 25

SP - 89

EP - 107

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 1

ER -

On the Length of a Random Minimum Spanning Tree

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this