Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Steiner minimal trees on zig-zag lines


Authors: D. Z. Du, F. K. Hwang and J. F. Weng
Journal: Trans. Amer. Math. Soc. 278 (1983), 149-156
MSC: Primary 05C05; Secondary 51M15
MathSciNet review: 697066
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] W. M. Boyce, An improved program for the full Steiner tree problem, Bell Lab. Tech. Memo., 1975.
  • [2] F. R. K. Chung and R. L. Graham, Steiner trees for ladders, Ann. Discrete Math. 2 (1978), 173–200. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976). MR 0480116
  • [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] Z. A. Melzak, On the problem of Steiner, Canad. Math. Bull. 4 (1961), 143–148. MR 0125466
  • [6] H. O. Pollak, Some remarks on the Steiner problem, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 278–295. MR 0491279
  • [7] J. M. Smith, Point set decomposition and suboptimal Steiner minimal trees, paper presented at the TIMS-ORSA Meeting, Colorado Springs, Colo., 1980.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C05, 51M15

Retrieve articles in all journals with MSC: 05C05, 51M15


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1983-0697066-5
Article copyright: © Copyright 1983 American Mathematical Society