Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Computation of minimal length full Steiner trees on the vertices of a convex polygon


Author: E. J. Cockayne
Journal: Math. Comp. 23 (1969), 521-531
MSC: Primary 05.45; Secondary 65.00
MathSciNet review: 0249323
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A Steiner minimal tree is a tree of minimal length whose vertices are a given set of points $ {a_1}, \cdots ,{a_n}$ in $ {E^2}$ and any set of additional points $ {s_1}, \cdots ,{s_k}(k \geqq 0)$. In general, the introduction of extra points makes possible shorter trees than the minimal length tree whose vertices are precisely $ {a_1}, \cdots ,{a_n}$ and for which practical algorithms are known. A Steiner minimal tree is the union of special subtrees, known as full Steiner trees. This paper demonstrates the use of the computer in generating minimal length full Steiner trees on sets of points in $ {E_2}$ which are the vertices of convex polygons. The procedure given is a basis from which further research might proceed towards an ultimate practical algorithm for the construction of Steiner minimal trees.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 05.45, 65.00

Retrieve articles in all journals with MSC: 05.45, 65.00


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1969-0249323-0
PII: S 0025-5718(1969)0249323-0
Article copyright: © Copyright 1969 American Mathematical Society