A probably fast, provably optimal algorithm for rectilinear Steiner trees

DOI10.1002/RSA.3240050405MaRDI QIDQ4312746zbMATH OpenOpenAlexFDO

Authors Linda L. Deneen, Gary M. Shute, 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

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

Recommendations

• Probabilistic partitioning algorithms for the rectilinear steiner problem
• Improved Computation of Optimal Rectilinear Steiner Minimal Trees
• Solving rectilinear Steiner tree problems exactly in theory and practice
• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
• scientific article; zbMATH DE number 1163724

Cites work

• A guided tour of Chernoff bounds
• An algorithm for the steiner problem in graphs
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• An SST-based algorithm for the steiner problem in graphs
• Fast heuristic algorithms for rectilinear Steiner trees
• scientific article; zbMATH DE number 3735154 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3384060 (Why is no real title available?)
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner’s Problem with Rectilinear Distance
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• Rectilinear steiner trees: Efficient special-case algorithms
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• The Rectilinear Steiner Tree Problem is NP-Complete
• The steiner problem in graphs
• Two probabilistic results on rectilinear Steiner trees
• Use of Steiner's problem in suboptimal routing in rectilinear metric

Cited in

(11)

• Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
• The Steiner tree problem in orientation metrics
• Computing optimal Steiner trees in polynomial space
• scientific article; zbMATH DE number 5313630 (Why is no real title available?)
• Faster Steiner Tree Computation in Polynomial-Space
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• scientific article; zbMATH DE number 742891 (Why is no real title available?)
• Definition and algorithms for reliable Steiner tree problem
• A rectilinear steiner minimal tree algorithm for convex point sets
• Logic Programming
• Rectilinear Steiner trees in narrow strips

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4312746)