William M. Boyce
- 1 BoYcs, W.M., AND SEERY, J.B. STEINER 72, an improved version of Coekayne and Schiller's program STEINER for the minimal network problem. Comptng. Sci. Tech. Rep. No. 35, Comptng. Sci. Res. Ctr., Bell Laboratories, Murray Hill, N.J.Google Scholar
- 2 CHUNG, F.R.K., AND GRAhAm, R.L. Steiner trees for ladders. Annals of Discrete Math.--Proc. Qualicum Beach Conf. To appear.Google Scholar
- 3 COCKAYNE, E J. Computation of minimal length full Steiner trees on the vertices of a convex polygon. Math. Comput. P8 (1969), 521-531Google Scholar
- 4 COCKAYNE, E.J. On the efficiency of the algorithm for Steiner minimal trees. SIAM J. Appl. Math. 18 (1970), 150-159.Google Scholar
- 5 COCKAYNE, E.J. On the Steiner problem. Canad. Math. Bull. 10 (1967), 431-450.Google Scholar
- 6 COCKAYNE, E J., AND SCHILLER, D.G. Computation of Steiner minimal trees. In Combinatorics, D.J A. Welsh and D.R. Woodall, Eds., Inst. Math. Appl., 1972, pp. 53-71 (FOR- TRAN IV program available on request from authors).Google Scholar
- 7 GILBERT, E.N., AND POLLAK, H.O. Steiner minimal trees. SIAM J. Appl. Math. 16 (1968), 1-29.Google Scholar
- 8 HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.Google Scholar
- 9 JOHNSON, S M. Generation of permutations by adjacent transportation. Math. Comput. 17 (1963), 282-285.Google Scholar
- 10 ME~ZAK, Z.A. On the problem of Steiner. Canad. Math. Bull. 4 (1961), 143-148.Google Scholar
- 11 PRIM, R.C. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36 (1957), 1389-1401.Google Scholar
Index Terms
- An Improved Program for the Full Steiner Tree Problem
Recommendations
On the hardness of full Steiner tree problems
Given a weighted graph G = ( V , E ) and a subset R of V, a Steiner tree in G is a tree which spans all vertices in R. The vertices in V R are called Steiner vertices. A full Steiner tree is a Steiner tree in which each vertex of R is a leaf. The full ...
The Euclidean Bottleneck Full Steiner Tree Problem
Given two sets in the plane, R of n (terminal) points and S of m (Steiner) points, a full Steiner tree is a Steiner tree in which all points of R are leaves. In the bottleneck full Steiner tree (BFST) problem, one has to find a full Steiner ...
The full Steiner tree problem
Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G=(V,E) with a length function on E and a proper subset R V, the problem is to find a full Steiner tree of ...
Comments