Tail bound for the minimal spanning tree of a complete graph

Jeong Han Kim; Sungchul Lee

doi:10.1016/S0167-7152(03)00208-6

Tail bound for the minimal spanning tree of a complete graph

Jeong Han Kim, Sungchul Lee

Department of Mathematics

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

9 Citations (Scopus)

Abstract

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

Original language	English
Pages (from-to)	425-430
Number of pages	6
Journal	Statistics and Probability Letters
Volume	64
Issue number	4
DOIs	https://doi.org/10.1016/S0167-7152(03)00208-6
Publication status	Published - 2003 Oct 1

All Science Journal Classification (ASJC) codes

Statistics and Probability
Statistics, Probability and Uncertainty

Access to Document

10.1016/S0167-7152(03)00208-6

Cite this

@article{30dbec0d93fd4863ba3f4b21035ff557,

title = "Tail bound for the minimal spanning tree of a complete graph",

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(α) of vertices of degree α in the minimal spanning tree of Kn. For a positive integer α, Aldous (Random Struct. Algorithms 1 (1990) 383) proved that the expectation of Nn(α) is asymptotically γ(α)n, where γ(α) is a function of α given by explicit integrations. We develop an algorithm to generate the minimal spanning tree and Chernoff-type tail bound for Nn(α).",

author = "Kim, {Jeong Han} and Sungchul Lee",

year = "2003",

month = oct,

day = "1",

doi = "10.1016/S0167-7152(03)00208-6",

language = "English",

volume = "64",

pages = "425--430",

journal = "Statistics and Probability Letters",

issn = "0167-7152",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Tail bound for the minimal spanning tree of a complete graph

AU - Kim, Jeong Han

AU - Lee, Sungchul

PY - 2003/10/1

Y1 - 2003/10/1

N2 - 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(α) of vertices of degree α in the minimal spanning tree of Kn. For a positive integer α, Aldous (Random Struct. Algorithms 1 (1990) 383) proved that the expectation of Nn(α) is asymptotically γ(α)n, where γ(α) is a function of α given by explicit integrations. We develop an algorithm to generate the minimal spanning tree and Chernoff-type tail bound for Nn(α).

AB - 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(α) of vertices of degree α in the minimal spanning tree of Kn. For a positive integer α, Aldous (Random Struct. Algorithms 1 (1990) 383) proved that the expectation of Nn(α) is asymptotically γ(α)n, where γ(α) is a function of α given by explicit integrations. We develop an algorithm to generate the minimal spanning tree and Chernoff-type tail bound for Nn(α).

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

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

U2 - 10.1016/S0167-7152(03)00208-6

DO - 10.1016/S0167-7152(03)00208-6

M3 - Article

AN - SCOPUS:0042884136

SN - 0167-7152

VL - 64

SP - 425

EP - 430

JO - Statistics and Probability Letters

JF - Statistics and Probability Letters

IS - 4

ER -

Tail bound for the minimal spanning tree of a complete graph

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this