Improved computation of plane Steiner Minimal Trees
Tóm tắt
ASteiner Minimal Tree (SMT) for a given setA = {a
1,...,a
n
} in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches, is minimum. To achieve the minimum, the tree may contain other points (Steiner points) besidesa
1,...,a
n
. Various improvements are presented to an earlier computer program of the authors for plane SMTs. These changes have radically reduced machine times. The existing program was limited in application to aboutn = 30, while the innovations have facilitated solution of many randomly generated 100-point problems in reasonable processing times.
Tài liệu tham khảo
M. W. Bern and R. L. Graham. The shortest network problem,Scientific American, January 1989, pp. 84–89.
W. M. Boyce and J. B. Seery. STEINER 72-An Improved Version of Cockayne and Schiller's Program STEINER for the Minimal Network Problem, Tech. Rept. No. 35, Dept. of Computer Science, Bell Laboratories, 1975.
W. M. Boyce and J. B. Seery. STEINER 73, Private communication.
E. J. Cockayne, On the efficiency of the algorithm for Steiner minimal trees,SIAM J. Appl. Math.,18(1) (1970), 150–159.
E. J. Cockayne and D. E. Hewgill, Exact computation of Steiner minimal trees in the plane,Inform. Process. Lett.,22 (1986), 151–156.
E. J. Cockayne and D. G. Schiller, Computation of Steiner minimal trees, in: D. J. A. Welsh and D. R. Woodall (eds.),Combinatorics, pp. 52–71, Inst. Math. Appl., Southend-on-Sea, Essex, 1972.
M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees,SIAM J. Appl. Math.,32(4) (1977), 835–859.
F. Hwang. A linear time algorithm for full Steiner trees,Oper. Res. Lett.,4(5) (1986), 235–237.
F. K. Hwang, G. D. Song, G. Y. Ting, and D. Z. Du. A decomposition theorem on Euclidean Steiner minimal trees,Discrete Comput. Geom.,3 (1988), 367–382.
Z. A. Melzak. On the problem of Steiner,Canad. Math. Bull,4 (1961), 143–148.
J. S. Provan. The role of Steiner hulls in the solution to Steiner tree problems,Ann. of Oper. Res. (to appear).
J. M. Smith, D. T. Lee, and J. S. Liebman. AnO(n logn) heuristic for Steiner minimal tree problems on the Euclidean metric,Networks,11 (1981), 23–29.
P. Winter. An algorithm for the Steiner problem in the Euclidean plane,Networks,15 (1985), 323–345.