Lower bounds for rectilinear Steiner trees in bounded space

DOI10.1016/0020-0190(91)90136-6MaRDI QIDQ750175zbMATH OpenOpenAlexFDO

Authors Timothy Law Snyder

Publication date 1991

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0020-0190(91)90136-6

zbMATH Keywords

combinatorial problemscomputational geometrylower boundsrectilinear Steiner treeworst-case

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner trees for bounded point sets
• On Steiner’s Problem with Rectilinear Distance
• On the Exact Location of Steiner Points in General Dimension
• Steiner Minimal Trees
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• The Rectilinear Steiner Tree Problem is NP-Complete
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• Two probabilistic results on rectilinear Steiner trees

Cited in

(6)

• Worst-case minimum rectilinear Steiner trees in all dimensions
• A note on lower bounds for rectilinear Steiner trees
• Minimum rectilinear Steiner tree of n points in the unit square
• A tight lower bound for planar Steiner orientation
• Embedding rectilinear Steiner trees with length restrictions
• scientific article; zbMATH DE number 2044939 (Why is no real title available?)

This page was built for publication: Lower bounds for rectilinear Steiner trees in bounded space

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