An O(N log N) minimal spanning tree algorithm for N points in the plane
From MaRDI portal
Publication:1082081
DOI10.1007/BF01939358zbMath0602.68053MaRDI QIDQ1082081
Ruei-Chuan Chang, Richard Chia-Tung Lee
Publication date: 1986
Published in: BIT (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
On a proposed divide-and-conquer minimal spanning tree algorithm ⋮ Kinetic Euclidean minimum spanning tree in the plane ⋮ A divide-and-conquer algorithm for constructing relative neighborhood graph ⋮ On the complexity of two circle connecting problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy
- Finding minimal spanning trees in a Euclidean coordinate space
- On the worst case of a minimal spanning tree algorithm for euclidean space
- A parallel algorithm for constructing minimum spanning trees
- Two algorithms for constructing a Delaunay triangulation
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces