Computing optimal rectilinear Steiner trees: A survey and experimental evaluation

DOI10.1016/S0166-218X(98)00089-4zbMath0916.90259MaRDI QIDQ1276966

Joseph L. Ganley

Publication date: 27 July 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

minimum-length rectilinear interconnectionrectilinear Steiner tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Computing optimal Steiner trees in polynomial space ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Definition and algorithms for reliable Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner tree problem
• Convexity and the Steiner tree problem
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• An SST-based algorithm for the steiner problem in graphs
• On Steiner Minimal Trees with Rectilinear Distance
• On the Average Number of Maxima in a Set of Vectors and Applications
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Faster exact algorithms for steiner trees in planar networks
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• Improved Computation of Optimal Rectilinear Steiner Minimal Trees
• Thirty‐five‐point rectilinear steiner minimal trees in a day
• Reductions for the rectilinear steiner tree problem
• On Steiner’s Problem with Rectilinear Distance
• Steiner's problem in graphs and its implications
• The steiner problem in graphs
• An algorithm for the steiner problem in graphs

This page was built for publication: Computing optimal rectilinear Steiner trees: A survey and experimental evaluation