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

MathSciNet review:
810173

Full-text PDF Free Access

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 which has been well studied in the literature.

**[1]**W. M. Boyce, M. R. Garey, and D. S. Johnson,*A note on bisecting minimum spanning trees*, Networks**8**(1978), no. 3, 187–192. MR**0491324****[2]**D. Z. Du and F. K. Hwang,*A new bound for the Steiner ratio*, Trans. Amer. Math. Soc.**278**(1983), no. 1, 137–148. MR**697065**, 10.1090/S0002-9947-1983-0697065-3**[3]**M. R. Garey, R. L. Graham, and D. S. Johnson,*The complexity of computing Steiner minimal trees*, SIAM J. Appl. Math.**32**(1977), no. 4, 835–859. MR**0443427****[4]**E. N. Gilbert and H. O. Pollak,*Steiner minimal trees*, SIAM J. Appl. Math.**16**(1968), 1–29. MR**0223269****[5]**R. L. Graham,*Some results on Steiner minimal trees*, unpublished manuscript.**[6]**Joseph B. Kruskal Jr.,*On the shortest spanning subtree of a graph and the traveling salesman problem*, Proc. Amer. Math. Soc.**7**(1956), 48–50. MR**0078686**, 10.1090/S0002-9939-1956-0078686-7**[7]**R. C. Prim,*Shortest connecting networks and some generalizations*, Bell System Tech. J.**36**(1957), 1389-1401.

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