{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T11:06:18Z","timestamp":1751367978544},"reference-count":64,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1991,1,1]],"date-time":"1991-01-01T00:00:00Z","timestamp":662688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1991,1]]},"DOI":"10.1007\/bf02061658","type":"journal-article","created":{"date-parts":[[2005,8,12]],"date-time":"2005-08-12T10:27:23Z","timestamp":1123842443000},"page":"73-84","source":"Crossref","is-referenced-by-count":9,"title":["A primer of the Euclidean Steiner problem"],"prefix":"10.1007","volume":"33","author":[{"given":"F. K.","family":"Hwang","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02061658_CR1","first-page":"1","volume":"12","author":"M. Ajtai","year":"1982","unstructured":"M. Ajtai, V. Chvatal, M.M. Newborn and E. Szemeredi, Crossing free subgraphs, Ann. Discr. Math. 12(1982)1\u201312.","journal-title":"Ann. Discr. Math."},{"key":"BF02061658_CR2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J. Beardwood","year":"1959","unstructured":"J. Beardwood, J.H. Halton and J.M. Hammersley, The shortest path through many points, Proc. Cambridge Phil. Soc. 55(1959)299\u2013327.","journal-title":"Proc. Cambridge Phil. Soc."},{"key":"BF02061658_CR3","doi-asserted-by":"crossref","unstructured":"M.W. Bern and R.L. Graham, The shortest-network problem, Sci. Amer. (Jan. 1989)84\u201389.","DOI":"10.1038\/scientificamerican0189-84"},{"key":"BF02061658_CR4","unstructured":"J.E. Beasley, A heuristic for the Euclidean and rectilinear Steiner tree problem, Working Paper, Managament School, Imperial College (1989)."},{"key":"BF02061658_CR5","doi-asserted-by":"crossref","unstructured":"R.S. Booth, Analytic formulas for full Steiner trees, Discr. Comput. Geom., to appear.","DOI":"10.1007\/BF02574675"},{"key":"BF02061658_CR6","doi-asserted-by":"crossref","unstructured":"R.S. Booth, The Steiner ratio for five points, Ann. Oper. Res., this volume.","DOI":"10.1007\/BF02071980"},{"key":"BF02061658_CR7","doi-asserted-by":"crossref","unstructured":"R.S. Booth and J.F. Weng, Steiner minimal trees for a class of zigzag lines, Algorithmica, to appear.","DOI":"10.1007\/BF01758760"},{"key":"BF02061658_CR8","unstructured":"W.M. Boyce and J.B. Seery, STEINER 72: An improved version of the minimal network problem, Memo,Bell Laboratories (1972)."},{"key":"BF02061658_CR9","doi-asserted-by":"crossref","unstructured":"W.M. Boyce, J.B. Seery and J.B. Goodman, Improved solutions for some minimal-network test problems, Memo, Bell Laboratories (1973).","DOI":"10.1145\/1217031.1217041"},{"key":"BF02061658_CR10","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1145\/321724.321733","volume":"19","author":"S.K. Chang","year":"1972","unstructured":"S.K. Chang, The generation of minimal trees with a Steiner topology, J. ACM 19(1972)699\u2013711.","journal-title":"J. ACM"},{"key":"BF02061658_CR11","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1080\/0025570X.1989.11977416","volume":"62","author":"F.R.K. Chung","year":"1989","unstructured":"F.R.K. Chung, M. Gardner and R.L. Graham, Steiner trees on a checkerboard, Math. Mag. 62(1989)83\u201396.","journal-title":"Math. Mag."},{"key":"BF02061658_CR12","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0167-5060(08)70332-7","volume":"2","author":"F.R.K. Chung","year":"1978","unstructured":"F.R.K. Chung and R.L. Graham, Steiner trees for ladders, Ann. Discr. Math. 2(1978)173\u2013200.","journal-title":"Ann. Discr. Math."},{"key":"BF02061658_CR13","first-page":"353","volume":"11","author":"F.R.K. Chung","year":"1981","unstructured":"F.R.K. Chung and R.L. Graham, On Steiner trees for bounded point sets, Geometriae Dedicata 11(1981)353\u2013361.","journal-title":"Geometriae Dedicata"},{"key":"BF02061658_CR14","first-page":"325","volume":"440","author":"F.R.K. Chung","year":"1985","unstructured":"F.R.K. Chung and R.L. Graham, A new bound for Euclidean Steiner minimal trees, Ann. N.Y. Acad. Sci. 440(1985)325\u2013346.","journal-title":"Ann. N.Y. Acad. Sci."},{"key":"BF02061658_CR15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1137\/0134003","volume":"34","author":"F.R.K. Chung","year":"1978","unstructured":"F.R.K. Chung and F.K. Hwang, A lower bound for the Steiner tree problem, SIAM J. Appl. Math. 34(1978)27\u201336.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02061658_CR16","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1137\/0118014","volume":"18","author":"E.J. Cockayne","year":"1970","unstructured":"E.J. Cockayne, On the efficiency of the algorithm for Steiner minimal trees, SIAM J. Appl. Math. 18(1970)150\u2013159.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02061658_CR17","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0020-0190(86)90062-1","volume":"22","author":"E.J. Cockayne","year":"1986","unstructured":"E.J. Cockayne and D.E. Hewgill, Exact computation of Steiner minimal trees in the plane, Inf. Proc. Lett. 22(1986)151\u2013156.","journal-title":"Inf. Proc. Lett."},{"key":"BF02061658_CR18","unstructured":"E.J. Cockayne and D.E. Hewgill, Leaf paths of full Steiner trees and computation of planar Steiner minimal trees, Preprint (1989)."},{"key":"BF02061658_CR19","unstructured":"E.J. Cockayne and D.G. Schiller, Computation of Steiner minimal trees, in:Combinatorics, ed. D.J.A. Welsh and D.R. Woodall (Int. Math. Appl., 1972), pp. 53\u201371."},{"key":"BF02061658_CR20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1090\/S0002-9947-1983-0697065-3","volume":"278","author":"D.Z. Du","year":"1983","unstructured":"D.Z. Du and F.K. Hwang, A new bound for the Steiner ratio, Trans. Amer. Math. Soc. 278(1983)137\u2013148.","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF02061658_CR21","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/BF02007669","volume":"3","author":"D.Z. Du","year":"1987","unstructured":"D.Z. Du and F.K. Hwang, Steiner minimal trees for bar waves, Acta Math. Appl. Sinica 3(1987)246\u2013256.","journal-title":"Acta Math. Appl. Sinica"},{"key":"BF02061658_CR22","doi-asserted-by":"crossref","unstructured":"D.Z. Du and F.K. Hwang, A proof of the Gilbert-Pollak conjecture on the Steiner ratio, Algorithmica, to appear.","DOI":"10.1007\/BF01758755"},{"key":"BF02061658_CR23","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1090\/S0002-9939-1985-0810173-6","volume":"95","author":"D.Z. Du","year":"1985","unstructured":"D.Z. Du, F.K. Hwang and S.C. Chao, Steiner minimal trees for points on a circle, Proc. Amer. Math. Soc. 95(1985)613\u2013618.","journal-title":"Proc. Amer. Math. Soc."},{"key":"BF02061658_CR24","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1090\/S0002-9947-1983-0697066-5","volume":"278","author":"D.Z. Du","year":"1983","unstructured":"D.Z. Du, F.K. Hwang and J.F. Weng, Steiner minimal trees on zigzag lines, Trans. Amer. Math. Soc. 278(1983)149\u2013156.","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF02061658_CR25","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF02187871","volume":"2","author":"D.Z. Du","year":"1987","unstructured":"D.Z. Du, F.K. Hwang and J.F. Weng, Steiner minimal trees on regular polygons, Discr. Comput. Geom. 2(1987)65\u201387.","journal-title":"Discr. Comput. Geom."},{"key":"BF02061658_CR26","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/0097-3165(85)90073-1","volume":"38","author":"D.Z. Du","year":"1985","unstructured":"D.Z. Du, F. K. Hwang and E.N. Yao, The Steiner ratio conjecture is true for five points, J. Combin. Theory Ser. A 38(1985)230\u2013240.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF02061658_CR27","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/0095-8956(82)90014-4","volume":"32","author":"D.Z. Du","year":"1982","unstructured":"D.Z. Du, E.N. Yao and F.K. Hwang, A short proof of a result of Pollak on Steiner minimal trees, J. Combin. Theory Ser. A 32(1982)356\u2013400.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF02061658_CR28","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1137\/0149057","volume":"49","author":"J. Friedel","year":"1989","unstructured":"J. Friedel and P. Widmayer, A simple proof of the Steiner ratio conjecture for five points, SIAM J. Appl. Math. 49(1989)960\u2013967.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02061658_CR29","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1112\/S0025579300000784","volume":"2","author":"L. Few","year":"1955","unstructured":"L. Few, The shortest path and shortest road throughn points, Mathematika 2(1955)141\u2013144.","journal-title":"Mathematika"},{"key":"BF02061658_CR30","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"M.R. Garey, R.L. Graham and D.S. Johnson, The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32(1977)835\u2013859.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02061658_CR31","unstructured":"R.L. Graham, Some results on Steiner minimal trees, Memo, Bell Laboratories (1967)."},{"key":"BF02061658_CR32","first-page":"177","volume":"4","author":"R.L. Graham","year":"1976","unstructured":"R.L. Graham and F.K. Hwang, Remarks on Steiner minimal trees I, Bull. Inst. Math. Acad. Sinica 4(1976)177\u2013182.","journal-title":"Bull. Inst. Math. Acad. Sinica"},{"key":"BF02061658_CR33","first-page":"323","volume":"16","author":"E.N. Gilbert","year":"1968","unstructured":"E.N. Gilbert and H.O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16(1968)323\u2013345.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02061658_CR34","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0167-6377(86)90008-8","volume":"5","author":"F.K. Hwang","year":"1986","unstructured":"F.K. Hwang, A linear time algorithm for full Steiner trees, Oper. Res. Lett. 5(1986)235\u2013237.","journal-title":"Oper. Res. Lett."},{"key":"BF02061658_CR35","unstructured":"F.K. Hwang, Steiner minimal trees on the Chinese checkerboard, Math. Mag., to appear."},{"key":"BF02061658_CR36","doi-asserted-by":"crossref","unstructured":"F.K. Hwang and D.S. Richards, Steiner tree problem, Networks, to appear.","DOI":"10.1002\/net.3230220105"},{"key":"BF02061658_CR37","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF02187919","volume":"3","author":"F.K. Hwang","year":"1988","unstructured":"F.K. Hwang, G.D. Song, G.Y. Ting and D.Z. Du, A decomposition theorem on Euclidean Steiner minimal trees, Discr. Comput. Geom. 3(1988)367\u2013382.","journal-title":"Discr. Comput. Geom."},{"key":"BF02061658_CR38","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/0012-365X(86)90040-3","volume":"62","author":"F.K. Hwang","year":"1986","unstructured":"F.K. Hwang and J.F. Weng, Hexagonal coordinate systems and Steiner minimal trees, Discr. Math. 62(1986)498\u2013557.","journal-title":"Discr. Math."},{"key":"BF02061658_CR39","unstructured":"F.K. Hwang and J.F. Weng, The shortest network with a given topology, Preprint (1988)."},{"key":"BF02061658_CR40","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0012-365X(83)90179-6","volume":"45","author":"F.K. Hwang","year":"1983","unstructured":"F.K. Hwang, J.F. Weng and D.Z. Du, A class of full Steiner minimal trees, Discr. Math. 45(1983) 107\u2013112.","journal-title":"Discr. Math."},{"key":"BF02061658_CR41","doi-asserted-by":"crossref","first-page":"223","DOI":"10.21136\/CPMF.1934.122548","volume":"63","author":"V. Jarnik","year":"1934","unstructured":"V. Jarnik and O. K\u00f6ssler, O minim\u00e1lnich grafesh obsahujicich n dan\u00fdch bodu, \u0108asopis P\u00east. Mat. Fys. 63(1934)223\u2013235.","journal-title":"\u0108asopis P\u00east. Mat. Fys."},{"key":"BF02061658_CR42","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R.M. Karp","year":"1977","unstructured":"R.M. Karp, Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane, Math. Oper. Res. 2(1977)209\u2013224.","journal-title":"Math. Oper. Res."},{"key":"BF02061658_CR43","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1093\/biomet\/72.1.191","volume":"72","author":"M. Lundy","year":"1985","unstructured":"M. Lundy, Applications of the annealing algorithm to combinatorial problems in statistics, Biometrika 72(1985)191\u2013198.","journal-title":"Biometrika"},{"key":"BF02061658_CR44","doi-asserted-by":"crossref","first-page":"143","DOI":"10.4153\/CMB-1961-016-2","volume":"4","author":"Z.A. Melzak","year":"1961","unstructured":"Z.A. Melzak, On the problem of Steiner, Can. Math. Bull. 4(1961)143\u2013148.","journal-title":"Can. Math. Bull."},{"key":"BF02061658_CR45","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0097-3165(78)90058-4","volume":"24","author":"H.O. Pollak","year":"1978","unstructured":"H.O. Pollak, Some remarks on the Steiner problem, J. Combin. Theory Ser. A 24(1978)278\u2013295.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF02061658_CR46","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230180108","volume":"18","author":"J.S. Provan","year":"1988","unstructured":"J.S. Provan, Convexity and the Steiner tree problem, Networks 18(1988)55\u201372.","journal-title":"Networks"},{"key":"BF02061658_CR47","doi-asserted-by":"crossref","unstructured":"J.S. Provan, The role of Steiner hulls in the solution to Steiner tree problems, Ann. Oper. Res., this volume.","DOI":"10.1007\/BF02067240"},{"key":"BF02061658_CR48","doi-asserted-by":"crossref","unstructured":"J.H. Rubinstein and D.A. Thomas, A variational approach to the Steiner network problem, Ann. Oper. Res., this volume.","DOI":"10.1007\/BF02071984"},{"key":"BF02061658_CR49","unstructured":"J.H. Rubinstein and D.A. Thomas, A variational approach to the Steiner ratio conjecture for six points, Preprint (1989)."},{"key":"BF02061658_CR50","unstructured":"J.H. Rubinstein and D.A. Thomas, The Steiner ratio conjecture for cocircular points, Preprint (1989)."},{"key":"BF02061658_CR51","doi-asserted-by":"crossref","unstructured":"J.H. Rubinstein and D.A. Thomas, Graham's problem on shortest networks for points on a circle, Algorithmica, to appear.","DOI":"10.1007\/BF01758758"},{"key":"BF02061658_CR52","doi-asserted-by":"crossref","unstructured":"M.I. Shamos and D. Hoey, Closest-point problems,16th Ann. Symp. on Foundations of Computer Science (1975), pp. 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF02061658_CR53","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230110104","volume":"11","author":"J.M. Smith","year":"1981","unstructured":"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\u201329.","journal-title":"Networks"},{"key":"BF02061658_CR54","unstructured":"W.D. Smith, Studies in discrete and computational geometry, Ph.D. Thesis, Program in Applied and Pure Mathematics, Princeton University (1988)."},{"key":"BF02061658_CR55","doi-asserted-by":"crossref","unstructured":"W.D. Smith, How to find Steiner minimal trees in Euclideand-space, Algorithmica, to appear.","DOI":"10.1007\/BF01758756"},{"key":"BF02061658_CR56","doi-asserted-by":"crossref","unstructured":"W.D. Smith and P.W. Shor, Steiner tree problems, Algorithmica, to appear.","DOI":"10.1007\/BF01758766"},{"key":"BF02061658_CR57","first-page":"37","volume":"22","author":"J. Soukup","year":"1977","unstructured":"J. Soukup, Minimum Steiner trees, roots of a polynomial and other magic, ACM\/SIGMAP Newsletter 22(1977)37\u201351.","journal-title":"ACM\/SIGMAP Newsletter"},{"key":"BF02061658_CR58","first-page":"48","volume":"15","author":"J. Soukup","year":"1973","unstructured":"J. Soukup and W.F. Chow, Set of test problems of the minimum length connection networks, SIGMAP Newsletter 15(1973)48\u201351.","journal-title":"SIGMAP Newsletter"},{"key":"BF02061658_CR59","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1214\/aop\/1176994411","volume":"9","author":"J.M. Steele","year":"1982","unstructured":"J.M. Steele, Subadditive Euclidean functionals and nonlinear growth in geometric probabilities, Ann. Prob. 9(1982)365\u2013376.","journal-title":"Ann. Prob."},{"key":"BF02061658_CR60","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1111\/j.1469-1809.1973.tb00595.x","volume":"36","author":"E.A. Thompson","year":"1973","unstructured":"E.A. Thompson, The method of minimum evolution, Ann. Human Genetics (London) 36(1973)333\u2013340.","journal-title":"Ann. Human Genetics"},{"key":"BF02061658_CR61","unstructured":"D. Trietsch and F.K. Hwang, An improved algorithm for Steiner trees, SIAM J. Appl. Math. 49(1989)."},{"key":"BF02061658_CR62","first-page":"153","volume":"7","author":"V.G. Vainer","year":"1978","unstructured":"V.G. Vainer, I.D. Zaitsev and \u00ca.M. Livshits, Design algorithms for connection networks, translated from Avtomatika i Telemekhanika 7(1978)153\u2013162.","journal-title":"translated from Avtomatika i Telemekhanika"},{"key":"BF02061658_CR63","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230150305","volume":"15","author":"P. Winter","year":"1985","unstructured":"P. Winter, An algorithm for the Steiner problem in the Euclidean plane, Networks 15(1985)323\u2013345.","journal-title":"Networks"},{"key":"BF02061658_CR64","unstructured":"W.C. Yu and S.B. Xu, The Steiner ratio conjecture on six points,Tienjing Conf. on Combinatorial Optimization, Tienjing, China (1988)."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02061658.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02061658\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02061658","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T12:08:41Z","timestamp":1626350921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02061658"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,1]]},"references-count":64,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,1]]}},"alternative-id":["BF02061658"],"URL":"https:\/\/doi.org\/10.1007\/bf02061658","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,1]]}}}