A probably fast, provably optimal algorithm for rectilinear Steiner trees

DOI10.1002/rsa.3240050405zbMath0822.68080OpenAlexW2037448683MaRDI QIDQ4312746

Gary M. Shute, Clark D. Thomborson, Linda L. Deneen

Publication date: 8 November 1994

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240050405

zbMATH Keywords

rectilinear Steiner minimal tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Computing optimal Steiner trees in polynomial space ⋮ The Steiner tree problem in orientation metrics ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ Computing optimal rectilinear Steiner trees: A survey and experimental evaluation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A guided tour of Chernoff bounds
• Two probabilistic results on rectilinear Steiner trees
• Fast heuristic algorithms for rectilinear Steiner trees
• 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
• 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
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• On Steiner’s Problem with Rectilinear Distance
• The steiner problem in graphs
• An algorithm for the steiner problem in graphs

This page was built for publication: A probably fast, provably optimal algorithm for rectilinear Steiner trees