Abstract
The Euclidean Steiner minimal tree problem is known to be an NP-complete problem and current alogorithms cannot solve problems with more than 30 points. Thus decomposition theorems can be very helpful in extending the boundary of workable problems. There have been only two known decomposition theorems in the literature. This paper provides a 50% increase in the reservoir of decomposition theorems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. J. Cockayne, On the efficiency of the algorithm for Steiner minimal trees,SIAM J. Appl. Math. 18 (1970), 150–159.
D. Z. Du, F. K. Hwang, and G. Y. Ting, Steiner minimal trees on sets of four points,Discrete Comput. Geom. to appear.
M. R. Garey, R. L. Graham, and D. S. Johnson, The complexity of computing Steiner minimal trees,SIAM J. Appl. Math. 32 (1977), 835–859.
E. N. Gilbert and H. O. Pollak, Steiner minimal trees,SIAM J. Appl. Math. 16 (1968), 1–29.
H. O. Pollak, Some remarks on the Steiner problem,J. Combin. Theory Ser. A 24 (1978), 279–295.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hwang, F.K., Song, G.D., Ting, G.Y. et al. A decomposition theorem on Euclidean Steiner minimal trees. Discrete Comput Geom 3, 367–382 (1988). https://doi.org/10.1007/BF02187919
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187919