A probably fast, provably optimal algorithm for rectilinear Steiner trees

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

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

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

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

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

Related Items

Computing optimal rectilinear Steiner trees: A survey and experimental evaluation, The Steiner tree problem in orientation metrics

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