An upper bound for the average length of the euclidean minimum spanning tree

DOI10.1080/00207168908803765zbMath0677.68060OpenAlexW2029868443WikidataQ126245740 ScholiaQ126245740MaRDI QIDQ3833626

Ruei-Chuan Chang, Ning-Yang Baby Wang

Publication date: 1989

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168908803765

zbMATH Keywords

Poisson distributionaverage case analysisEuclidean minimum spanning treeordered statisticsETSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05)

Related Items

Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space, An average case analysis of a greedy algorithm for the on-line Steiner tree problem, Randomized algorithms for the on-line minimum matching problem on euclidean space

Cites Work

• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• A Lower Bound for the Expected Travel Among $m$ Random Points