Steiner minimal tree for points on a circle

Du, D. Z.; Hwang, F. K.; Chao, S. C.

doi:10.1090/S0002-9939-1985-0810173-6

Steiner minimal tree for points on a circle
HTML articles powered by AMS MathViewer

by D. Z. Du, F. K. Hwang and S. C. Chao PDF

Proc. Amer. Math. Soc. 95 (1985), 613-618 Request permission

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

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 491324, DOI 10.1002/net.3230080302
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, DOI 10.1090/S0002-9947-1983-0697065-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 443427, DOI 10.1137/0132072
E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16 (1968), 1–29. MR 223269, DOI 10.1137/0116001

Some results on Steiner minimal trees

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 78686, DOI 10.1090/S0002-9939-1956-0078686-7

Shortest connecting networks and some generalizations

36