Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Steiner minimal tree for points on a circle


Authors: D. Z. Du, F. K. Hwang and S. C. Chao
Journal: Proc. Amer. Math. Soc. 95 (1985), 613-618
MSC: Primary 05C05; Secondary 52A40, 94C15
DOI: https://doi.org/10.1090/S0002-9939-1985-0810173-6
MathSciNet review: 810173
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the Steiner minimal tree for a set of points on a circle is the shortest path connecting them if at most one distance between two consecutive points is "large". We prove this by making an interesting use of the Steiner ratio $ \rho $ which has been well studied in the literature.


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

  • [1] W. M. Boyce, M. R. Garey and D. S. Johnson, A note on bisecting minimal spanning trees, Networks 8 (1978), 187-192. MR 0491324 (58:10587)
  • [2] D. Z. Du and F. K. Hwang, A new bound for the Steiner ratio, Trans. Amer. Math. Soc. 278 (1983), 137-148. MR 697065 (85i:05080a)
  • [3] M. R. Garey, R. L. Graham and D. S. Johnson, The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32 (1977), 835-859. MR 0443427 (56:1797)
  • [4] E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16 (1968), 1-29. MR 0223269 (36:6317)
  • [5] R. L. Graham, Some results on Steiner minimal trees, unpublished manuscript.
  • [6] J. B. Kruskal, On the shortest spanning subtree of a graph, Proc. Amer. Math. Soc. 7 (1956), 48-50. MR 0078686 (17:1231d)
  • [7] R. C. Prim, Shortest connecting networks and some generalizations, Bell System Tech. J. 36 (1957), 1389-1401.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C05, 52A40, 94C15

Retrieve articles in all journals with MSC: 05C05, 52A40, 94C15


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1985-0810173-6
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society