Remote Access Transactions of the American Mathematical Society
Green Open Access

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

Article copyright: © Copyright 1983 American Mathematical Society