Computation of minimal length full Steiner trees on the vertices of a convex polygon
Author:
E. J. Cockayne
Journal:
Math. Comp. 23 (1969), 521531
MSC:
Primary 05.45; Secondary 65.00
MathSciNet review:
0249323
Fulltext 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 in and any set of additional points . In general, the introduction of extra points makes possible shorter trees than the minimal length tree whose vertices are precisely 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 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.
 [1]
E.
J. Cockayne, On the Steiner problem, Canad. Math. Bull.
10 (1967), 431–450. MR 0215750
(35 #6585)
 [2]
E.
J. Cockayne and Z.
A. Melzak, Steiner’s problem for setterminals, Quart.
Appl. Math. 26 (1968), 213–218. MR 0233286
(38 #1608)
 [3]
Richard
Courant and Herbert
Robbins, What Is Mathematics?, Oxford University Press, New
York, 1941. MR
0005358 (3,144b)
 [4]
E.
N. Gilbert and H.
O. Pollak, Steiner minimal trees, SIAM J. Appl. Math.
16 (1968), 1–29. MR 0223269
(36 #6317)
 [5]
Z.
A. Melzak, On the problem of Steiner, Canad. Math. Bull.
4 (1961), 143–148. MR 0125466
(23 #A2767)
 [6]
Ivan Niven, Mathematics of Choice, or How to Count Without Counting, Random House, New York, 1965.
 [7]
R. C. Prim, "Shortest connecting networks," Bell System Tech. J., v. 31, pp. 13981401.
 [1]
 E. J. Cockayne, "On the Steiner problem," Canad. Math. Bull., v. 10, 1967, pp. 431450. MR 35 #6585. MR 0215750 (35:6585)
 [2]
 E. J. Cockayne & Z. A. Melzak, "On Steiner's problem for setrterminals," Quart. Appl. Math. (To appear.) MR 0233286 (38:1608)
 [3]
 R. Courant & H. Robbins, What is Mathematics, Oxford Univ. Press, New York, 1941. MR 3, 144. MR 0005358 (3:144b)
 [4]
 E. N. Gilbert & H. 0. Pollak, "Steiner minimal trees," SIAM J. Appl. Math., v. 16, 1968, pp. 129. MR 36 #6317. MR 0223269 (36:6317)
 [5]
 Z. A. Melzak, "On the problem of Steiner," Canad. Math. Bull., v. 4, 1961, pp. 143148. MR 23 #A2767. MR 0125466 (23:A2767)
 [6]
 Ivan Niven, Mathematics of Choice, or How to Count Without Counting, Random House, New York, 1965.
 [7]
 R. C. Prim, "Shortest connecting networks," Bell System Tech. J., v. 31, pp. 13981401.
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/S00255718196902493230
PII:
S 00255718(1969)02493230
Article copyright:
© Copyright 1969
American Mathematical Society
