THE MINIMAL SPANNING TREE IN A COMPLETE GRAPH AND A FUNCTIONAL LIMIT-THEOREM FOR TREES IN A RANDOM GRAPH

Authors
JANSON S
Citation
S. Janson, THE MINIMAL SPANNING TREE IN A COMPLETE GRAPH AND A FUNCTIONAL LIMIT-THEOREM FOR TREES IN A RANDOM GRAPH, Random structures & algorithms, 7(4), 1995, pp. 337-355
Citations number
11
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
7
Issue
4
Year of publication
1995
Pages
337 - 355
Database
ISI
SICI code
1042-9832(1995)7:4<337:TMSTIA>2.0.ZU;2-9
Abstract
The minimal weight of a spanning tree in a complete graph K-n with ind ependent, uniformly distributed random weights on the edges is shown t o have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution o f the number of tree components of given sizes in a random graph. (C) 1995 John Wiley & Sons, Inc.