Two probabilistic results on rectilinear Steiner trees

DOI10.1007/BF01762114zbMATH Open0648.90080MaRDI QIDQ1105495FDOQ1105495

Authors: M. W. Bern 

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

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

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)

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Title not available (Why is that?)
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On Steiner trees for bounded point sets
• Title not available (Why is that?)
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• On Steiner Minimal Trees with Rectilinear Distance
• Use of Steiner's problem in suboptimal routing in rectilinear metric
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• Title not available (Why is that?)
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• Title not available (Why is that?)
• Rectilinear steiner trees: Efficient special-case algorithms

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
• Title not available (Why is that?)
• 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)