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

**[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.

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