Fast heuristic algorithms for rectilinear Steiner trees
From MaRDI portal
Publication:1118419
DOI10.1007/BF01553886zbMath0668.68075MaRDI QIDQ1118419
Publication date: 1989
Published in: Algorithmica (Search for Journal in Brave)
VLSI design; heuristic algorithms; computational geometry; minimum spanning tree; Steiner tree; efficient algorithm; average case analysis; rectilinear distance; rectilinear metric
68R10: Graph theory (including graph drawing) in computer science
Related Items
A probably fast, provably optimal algorithm for rectilinear Steiner trees, A heuristic for Euclidean and rectilinear Steiner problems, Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study, Tree polytope on 2-trees, Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, The Steiner tree problem in orientation metrics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time algorithm for full Steiner trees
- Exact computation of Steiner minimal trees in the plane
- Hexagonal coordinate systems and Steiner minimal trees
- A fast algorithm for Steiner trees
- On Steiner trees for bounded point sets
- The Steiner problem in phylogeny is NP-complete
- Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
- On finding steiner vertices
- Probabilistic partitioning algorithms for the rectilinear steiner problem
- On Steiner Minimal Trees with Rectilinear Distance
- Use of Steiner's problem in suboptimal routing in rectilinear metric
- Rectilinear steiner trees: Efficient special-case algorithms
- An O(n log n) algorithm for suboptimal rectilinear Steiner trees
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
- The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
- The computation of nearly minimal Steiner trees in graphs
- On the History of the Minimum Spanning Tree Problem
- On Steiner’s Problem with Rectilinear Distance
- Random Minimal Trees
- Steiner Minimal Trees
- An algorithm for the steiner problem in graphs
- An algorithm for the steiner problem in graphs
- A faster approximation algorithm for the Steiner problem in graphs