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?)

  • [1] F. R. K. Chung and F. K. Hwang, A lower bound for the Steiner tree problem, SIAM J. Appl. Math. 34 (1978), 27-36. MR 482833 (81h:05052)
  • [2] E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16 (1968), 1-29. MR 0223269 (36:6317)
  • [3] R. L. Graham and F. K. Hwang, Remarks on Steiner minimal trees. I, Bull. Inst. Math. Acad. Sinica 4 (1976), 177-182. MR 0437371 (55:10302)
  • [4] Z. A. Melzak, On the problem of Steiner, Canad. Math. Bull. 4 (1961), 143-148. MR 0125466 (23:A2767)
  • [5] H. O. Pollak, Some remarks on the Steiner problem, J. Combin. Theory Ser. A 24 (1978), 278-295. MR 0491279 (58:10543)

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

American Mathematical Society