Abstract
LetP be a set ofn points on the euclidean plane. LetL s(P) andL m (P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,L s (P)≥(√3/2)L m (P). We provide a proof for their conjecture in this paper.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
F. R. K. Chung and E. N. Gilbert, Steiner trees for the regular simplex,Bull Inst. Math. Acad. Sinica,4, 313–325, 1976.
F. R. K. Chung and R. L. Graham, A new bound for euclidean Steiner minimum trees,Ann. N.Y. Acad. Sci.,440, 328–346, 1985.
F. R. K. Chung and F. K. Hwang, A lower bound for the Steiner tree problem,SIAM J. Appl. Math.,34, 27–36, 1978.
D. Z. Du and F. K. Hwang, A new bound for the Steiner ratio,Trans. Amer. Math. Soc.,278, 137–148, 1983.
D. Z. Du, F. K. Hwang, and E. N. Yao, The Steiner ratio conjecture is true for five points,J. Combinatorial Theory, Ser. A,32, 396–400, 1985.
M. R. Garey, R. L. Graham and D. S. Johnson, The complexity of computing Steiner minimal trees,SIAM J. Appl. Math.,32, 835–859, 1977.
E. N. Gilbert and H. O. Pollak, Steiner minimal trees,SIAM J. Appl. Math.,16, 1–29, 1966.
R. L. Graham and F. K. Hwang, Remarks on Steiner minimal trees,Bull. Inst. Math. Acad. Sinica,4, 177–182, 1976.
F. K. Hwang, On Steiner minimal trees with rectilinear distance,SIAM J. Appl. Math.,30, 104–114, 1976.
Z. C. Liu and D. Z. Du, On Steiner minimal trees with L p distance,Algorithmica, to appear.
H. O. Pollak, Some remarks on the Steiner problem,J. Combinatorial Theory, Ser. A,24, 278–295, 1978.
J. H. Rubinstein and D. A. Thomas, A variational approach to the Steiner network problem,Proceedings of NATO Workshop on Topological Networks, Copenhagen, Denmark, 1989.
J. H. Rubinstein and D. A. Thomas, The Steiner ratio conjecture for six points,J. Combinatoria Theory, Ser. A., to appear.
W. D. Smith, How to find Steiner minimal trees in euclideand-space,Algorithmica, to appear.
J. F. Weng, Steiner problem in hexagonal metric, unpublished manuscript.
Author information
Authors and Affiliations
Additional information
Communicated by F. K. Hwang.
supported by NSF under grant STC88-09648.
supported in part by the National Natural Science Foundation of China.
Rights and permissions
About this article
Cite this article
Du, D.Z., Hwang, F.K. A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica 7, 121–135 (1992). https://doi.org/10.1007/BF01758755
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01758755