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

heuristicminimal spanning treeNP- completeminimal overall lengthRectilinear Steiner TreeSteiner Points

Mathematics Subject Classification ID

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

Related Items

Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, On nearest-neighbor graphs, The Steiner tree problem in orientation metrics, On nearest-neighbor graphs, A probably fast, provably optimal algorithm for rectilinear Steiner trees, 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, Light orthogonal networks with constant geometric dilation, Lower bounds for rectilinear Steiner trees in bounded space, Steiner tree problems, Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study

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