A simple proof of the planar rectilinear Steiner ratio

DOI10.1016/0167-6377(92)90053-6MaRDI QIDQ1200801zbMATH OpenOpenAlexFDO

Authors Jeffrey S. Salowe

Publication date 16 January 1993

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(92)90053-6

zbMATH Keywords

distance algorithmsheuristicsrectilinear minimum spanning treerectilinear Steiner ratiotree algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Thek-Steiner Ratio in the Rectilinear Plane
• A simple proof of Hwang's theorem for rectilinear Steiner minimal trees
• The Steiner ratio conjecture of Gilbert and Pollak is true.
• Worst-case ratios of networks in the rectilinear plane
• A tight lower bound for the Steiner ratio in Minkowski planes

Cites work

• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• A simple proof of Hwang's theorem for rectilinear Steiner minimal trees
• An 11/6-approximation algorithm for the network Steiner problem
• scientific article; zbMATH DE number 742979 (Why is no real title available?)
• On Steiner Minimal Trees with Rectilinear Distance

Cited in

(5)

• A simple proof of Hwang's theorem for rectilinear Steiner minimal trees
• 1-line minimum rectilinear Steiner trees and related problems
• Worst-case ratios of networks in the rectilinear plane
• Thek-Steiner Ratio in the Rectilinear Plane
• scientific article; zbMATH DE number 776081 (Why is no real title available?)

This page was built for publication: A simple proof of the planar rectilinear Steiner ratio

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