On the Length of a Random Minimum Spanning Tree

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)89-107
Number of pages19
JournalCombinatorics Probability and Computing
Volume25
Issue number1
DOIs
StatePublished - Jan 1 2016

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'On the Length of a Random Minimum Spanning Tree'. Together they form a unique fingerprint.

Cite this