Tail bound for the minimal spanning tree of a complete graph

Jeong Han Kim and Sungchul Lee

Statistics & Probability Letters, 2003, vol. 64, issue 4, 425-430

Abstract: Suppose each edge of the complete graph Kn is assigned a random weight chosen independently and uniformly from the unit interval [0,1]. A minimal spanning tree is a spanning tree of Kn with the minimum weight. It is easy to show that such a tree is unique almost surely. This paper concerns the number Nn([alpha]) of vertices of degree [alpha] in the minimal spanning tree of Kn. For a positive integer [alpha], Aldous (Random Struct. Algorithms 1 (1990) 383) proved that the expectation of Nn([alpha]) is asymptotically [gamma]([alpha])n, where [gamma]([alpha]) is a function of [alpha] given by explicit integrations. We develop an algorithm to generate the minimal spanning tree and Chernoff-type tail bound for Nn([alpha]).

Keywords: Minimal; spanning; tree; Large; deviation; Martingale; inequality (search for similar items in EconPapers)
Date: 2003
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167-7152(03)00208-6
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:stapro:v:64:y:2003:i:4:p:425-430

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Statistics & Probability Letters is currently edited by Somnath Datta and Hira L. Koul

More articles in Statistics & Probability Letters from Elsevier
Bibliographic data for series maintained by Catherine Liu ().