Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
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
  • © Copyright 1983 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 278 (1983), 149-156
  • MSC: Primary 05C05; Secondary 51M15
  • DOI: https://doi.org/10.1090/S0002-9947-1983-0697066-5
  • MathSciNet review: 697066