Fast heuristic algorithms for rectilinear Steiner trees

DOI10.1007/BF01553886zbMath0668.68075MaRDI QIDQ1118419

D. S. Richards

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

VLSI designheuristic algorithmscomputational geometryminimum spanning treeSteiner treeefficient algorithmaverage case analysisrectilinear distancerectilinear metric

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (9)

Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors ⋮ The Steiner tree problem in orientation metrics ⋮ A probably fast, provably optimal algorithm for rectilinear Steiner trees ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ A heuristic for Euclidean and rectilinear Steiner problems ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study ⋮ Tree polytope on 2-trees

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

This page was built for publication: Fast heuristic algorithms for rectilinear Steiner trees