Steiner minimal trees on zig-zag lines

Du, D. Z.; Hwang, F. K.; Weng, J. F.

doi:10.1090/S0002-9947-1983-0697066-5

Steiner minimal trees on zig-zag lines
HTML articles powered by AMS MathViewer

by D. Z. Du, F. K. Hwang and J. F. Weng PDF

Trans. Amer. Math. Soc. 278 (1983), 149-156 Request permission

Abstract:

A Steiner minimal tree for a given set $P$ of points in the Euclidean plane is a shortest network interconnecting $P$ whose vertex set may include some additional points. The construction of Steiner minimal trees has been proved to be an $NP$-complete problem for general $P$. However, the $NP$-completeness does not exclude the possibility that Steiner trees for sets of points with special structures can be efficiently determined. In this paper we determine the Steiner mimmal trees for zig-zag lines with certain regularity properties. We also give an explicit formula for the length of such a tree.

References

An improved program for the full Steiner tree problem

F. R. K. Chung and R. L. Graham, Steiner trees for ladders, Ann. Discrete Math. 2 (1978), 173–200. MR 480116
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
Z. A. Melzak, On the problem of Steiner, Canad. Math. Bull. 4 (1961), 143–148. MR 125466, DOI 10.4153/CMB-1961-016-2
H. O. Pollak, Some remarks on the Steiner problem, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 278–295. MR 491279, DOI 10.1016/0097-3165(78)90058-4

Point set decomposition and suboptimal Steiner minimal trees