Worst-case minimum rectilinear Steiner trees in all dimensions

DOI10.1007/BF02293036zbMath0783.05041OpenAlexW2764860633MaRDI QIDQ1192611

Timothy Law Snyder

Publication date: 27 September 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02293036

zbMATH Keywords

Steiner treeManhattan metric

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27)

Related Items

Minimum rectilinear Steiner tree of \(n\) points in the unit square

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds for rectilinear Steiner trees in bounded space
• On the length of optimal TSP circuits in sets of bounded diameter
• Two probabilistic results on rectilinear Steiner trees
• Quantizers ad the worst case Euclidean traveling salesman problem
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• On Steiner trees for bounded point sets
• Worst-case greedy matchings in the unitd-cube
• The shortest path and the shortest road through n points
• On the Problem of Steiner
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• On the Exact Location of Steiner Points in General Dimension
• Locating the vertices of a steiner tree in an arbitrary metric space
• On Steiner Minimal Trees with Rectilinear Distance
• 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
• How Long Can a Euclidean Traveling Salesman Tour Be?
• On Steiner’s Problem with Rectilinear Distance
• Steiner Minimal Trees