Two probabilistic results on rectilinear Steiner trees

DOI10.1007/BF01762114zbMath0648.90080MaRDI QIDQ1105495

Marshall W. Bern

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

heuristic; minimal spanning tree; NP- complete; minimal overall length; Rectilinear Steiner Tree; Steiner Points

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

Related Items

A probably fast, provably optimal algorithm for rectilinear Steiner trees, Steiner tree problems, Lower bounds for rectilinear Steiner trees in bounded space, Comments on Bern's probabilistic results on rectilinear Steiner trees, Worst-case minimum rectilinear Steiner trees in all dimensions, Heuristics for the Steiner problem in graphs, Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study, Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, On nearest-neighbor graphs, The Steiner tree problem in orientation metrics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• On Steiner trees for bounded point sets
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• 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