An algorithm for geometric minimum spanning trees requiring nearly linear expected time

DOI10.1007/BF01553902zbMath0682.68042OpenAlexW2075773495MaRDI QIDQ1824386

Kenneth L. Clarkson

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553902

zbMATH Keywords

minimum spanning treelinear expected time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Some new exact solutions of \((3+1)\)-dimensional Burgers system via Lie symmetry analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Moment inequalities for random variables in computational geometry
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Optimal Expected-Time Algorithms for Closest Point Problems
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

This page was built for publication: An algorithm for geometric minimum spanning trees requiring nearly linear expected time