Tail bound for the minimal spanning tree of a complete graph.

DOI10.1016/S0167-7152(03)00208-6zbMath1116.60304OpenAlexW1998533063MaRDI QIDQ1423115

Sungchul Lee, Jeong Han Kim

Publication date: 14 February 2004

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-7152(03)00208-6

zbMATH Keywords

Minimal spanning treeLarge deviationMartingale inequality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Large deviations (60F10)

Related Items (1)

Comparison of Proximity Measures for a Topological Discrimination

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• On the value of a random minimum spanning tree problem
• The central limit theorem for Euclidean minimal spanning trees. I
• The central limit theorem for weighted minimal spanning trees on random points
• On the number of leaves of a euclidean minimal spanning tree
• A random tree model associated with random graphs
• On Brooks' Theorem for Sparse Graphs
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The central limit theorem for Euclidean minimal spanning trees II

This page was built for publication: Tail bound for the minimal spanning tree of a complete graph.