Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
From MaRDI portal
Publication:1343464
DOI10.1007/BF01188713zbMath0823.68108OpenAlexW2011014777MaRDI QIDQ1343464
S. S. Ravi, Seth Chaiken, Young C. Wee
Publication date: 19 January 1995
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01188713
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)
Related Items
On the symmetric angle-restricted nearest neighbor problem, Minimum rectilinear Steiner tree of \(n\) points in the unit square, Light orthogonal networks with constant geometric dilation
Cites Work
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- Parallel algorithms for the segment dragging problem
- The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
- Two probabilistic results on rectilinear Steiner trees
- Parallel computational geometry
- Fast heuristic algorithms for rectilinear Steiner trees
- The relative neighbourhood graph of a finite planar set
- Decomposable searching problems
- The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
- New Data Structures for Orthogonal Range Queries
- Batched dynamic solutions to decomposable searching problems
- Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Dynamic Steiner Tree Problem
- An O(n log n) algorithm for suboptimal rectilinear Steiner trees
- Steiner tree problems