Two probabilistic results on rectilinear Steiner trees

DOI10.1007/BF01762114MaRDI QIDQ1105495zbMATH OpenFDO

Authors M. W. Bern

Publication date 1988

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

heuristicminimal spanning treeNP- completeminimal overall lengthRectilinear Steiner TreeSteiner Points

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fast heuristic algorithms for rectilinear Steiner trees
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
• scientific article; zbMATH DE number 1185330
• Thirty‐five‐point rectilinear steiner minimal trees in a day

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3138432 (Why is no real title available?)
• scientific article; zbMATH DE number 3932819 (Why is no real title available?)
• scientific article; zbMATH DE number 3735154 (Why is no real title available?)
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner trees for bounded point sets
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• Rectilinear steiner trees: Efficient special-case algorithms
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• 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
• Use of Steiner's problem in suboptimal routing in rectilinear metric

Cited in

(17)

• The Steiner tree problem in orientation metrics
• Comments on Bern's probabilistic results on rectilinear Steiner trees
• Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
• Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study
• Fast heuristic algorithms for rectilinear Steiner trees
• Light orthogonal networks with constant geometric dilation
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• On nearest-neighbor graphs
• scientific article; zbMATH DE number 1185330 (Why is no real title available?)
• On nearest-neighbor graphs
• Steiner tree problems
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• Bounding the expected number of rectilinear full Steiner trees
• Lower bounds for rectilinear Steiner trees in bounded space
• Worst-case minimum rectilinear Steiner trees in all dimensions
• Heuristics for the Steiner problem in graphs
• Probability of diameter two for Steinhaus graphs

This page was built for publication: Two probabilistic results on rectilinear Steiner trees

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