Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

A new bound for the Steiner ratio


Authors: D. Z. Du and F. K. Hwang
Journal: Trans. Amer. Math. Soc. 278 (1983), 137-148
MSC: Primary 05C05; Secondary 51M15
MathSciNet review: 697065
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ V$ denote a given set of $ n$ points in the euclidean plane. A Steiner minimal tree for $ V$ is the shortest network (clearly, it has to be a tree) interconnecting $ V$. Junctions of the network which are not in $ V$ are called Steiner points (those in $ V$ will be called regular points). A shortest tree interconnecting $ V$ without using any Steiner points is called a minimal tree. Let $ \sigma (V)$ and $ \mu (V)$ denote the lengths of a Steiner minimal tree and a minimal tree, respectively. Define $ \rho $ to be the greatest lower bound for the ratio $ \sigma (V)/\mu (V)$ over all $ V$. We prove $ \rho > .8$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C05, 51M15

Retrieve articles in all journals with MSC: 05C05, 51M15


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1983-0697065-3
PII: S 0002-9947(1983)0697065-3
Article copyright: © Copyright 1983 American Mathematical Society