{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,15]],"date-time":"2026-02-15T08:46:42Z","timestamp":1771145202379,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01758756","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T10:49:08Z","timestamp":1118832548000},"page":"137-177","source":"Crossref","is-referenced-by-count":107,"title":["How to find Steiner minimal trees in euclideand-space"],"prefix":"10.1007","volume":"7","author":[{"given":"Warren D.","family":"Smith","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01758756_CR1","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/net.3230070104","volume":"7","author":"A. V. Aho","year":"1977","unstructured":"A. V. Aho, M. R. Garey, and F. K. Hwang: Rectilinear Steiner trees: Efficient special case algorithms,Networks,7 (1977), 37\u201358.","journal-title":"Networks"},{"key":"BF01758756_CR2","first-page":"9","volume":"12","author":"M. Ajtai","year":"1982","unstructured":"M. Ajtai, V. Chvatal, M. M. Newborn, and E. Szemeredi: Crossing free subgraphs,Ann. Discrete Math.,12 (1982), 9\u201312.","journal-title":"Ann. Discrete Math."},{"key":"BF01758756_CR3","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. Assoc. Comput. Math.,19 (1972), 699\u2013711.","journal-title":"J. Assoc. Comput. Math."},{"key":"BF01758756_CR4","first-page":"313","volume":"4","author":"F. R. K. Chung","year":"1976","unstructured":"F. R. K. Chung and E. N. Gilbert: Steiner trees for the regular simplex,Bull. Inst. Math. Acad. Sinica,4 (1976), 313\u2013325.","journal-title":"Bull. Inst. Math. Acad. Sinica"},{"key":"BF01758756_CR5","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1111\/j.1749-6632.1985.tb14564.x","volume":"440","author":"F. R. K. Chung","year":"1985","unstructured":"F. R. K. Chung and R. L. Graham: A new bound for Euclidean Steiner trees,Ann. N. Y. Acad. Sci,440 (1985), 328\u2013346.","journal-title":"Ann. N. Y. Acad. Sci"},{"key":"BF01758756_CR6","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1080\/0025570X.1972.11976242","volume":"45","author":"E. J. Cockayne","year":"1972","unstructured":"E. J. Cockayne: On Fermat's problem on the surface of a sphere,Math. Mag.,45 (1972), 216\u2013219.","journal-title":"Math. Mag."},{"key":"BF01758756_CR7","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,Inform. Process. Lett.,22 (1986), 151\u2013156.","journal-title":"Inform. Process. Lett."},{"key":"BF01758756_CR8","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/net.3230110407","volume":"11","author":"U. Derigs","year":"1981","unstructured":"U. Derigs: A shortest augmenting path method for solving minimum perfect matching problems,Networks,11 (1981), 379\u2013390.","journal-title":"Networks"},{"key":"BF01758756_CR9","volume-title":"On Steiner ratio conjectures, manuscript","author":"D. Z. Du","year":"1989","unstructured":"D. Z. Du: On Steiner ratio conjectures, manuscript, Inst. Appl. Math. Academia Sinica, Beijing, China, 1989."},{"key":"BF01758756_CR10","unstructured":"D. Z. Du: The Steiner ratio conjecture is true for six points, to be published."},{"issue":"1","key":"BF01758756_CR11","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 for regular polygons,Discrete Comput. Geom.,2, 1 (1987), 65\u201387.","journal-title":"Discrete Comput. Geom."},{"key":"BF01758756_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner:Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1987."},{"issue":"3","key":"BF01758756_CR13","first-page":"209","volume":"3","author":"J. H. Friedman","year":"1977","unstructured":"J. H. Friedman, J. L. Bentley, and R. A. Finkel: An algorithm for performing best matches in logarithmic expected time,ACMTOMS,3, 3 (1977), 209\u2013226.","journal-title":"ACMTOMS"},{"key":"BF01758756_CR14","first-page":"835","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"M. R. Garey and D. S. Johnson: The complexity of computing Steiner minimum trees,SIAM J. Algebraic Discrete Methods,32 (1977), 835\u2013859.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"BF01758756_CR15","first-page":"826","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"M. R. Garey and D. S. Johnson: The rectilinear Steiner minimum tree problem is NP-completeSIAM J. Algebraic Discrete Methods,32 (1977), 826\u2013834.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"118","key":"BF01758756_CR16","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1090\/S0025-5718-1972-0314226-X","volume":"26","author":"E. Gekeler","year":"1972","unstructured":"E. Gekeler: On the solution of systems of equations by the epsilon algorithm of Wynn,Math. Comp.,26, 118 (1972), 427\u2013436.","journal-title":"Math. Comp."},{"key":"BF01758756_CR17","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/0196-6774(87)90032-0","volume":"8","author":"G. Georgakopoulos","year":"1987","unstructured":"G. Georgakopoulos and C. H. Papadimitriou: The 1-Steiner tree problem,J. Algorithms, 8 (1987), 122\u2013130.","journal-title":"J. Algorithms"},{"key":"BF01758756_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","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), 1\u201329.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01758756_CR19","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":"BF01758756_CR20","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M. Hanan","year":"1966","unstructured":"M. Hanan: On Steiner's problem with rectilinear distance,SIAM J. Appl. Math.,14 (1966), 255\u2013265.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01758756_CR21","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01585505","volume":"7","author":"K. Heibig-Hansen","year":"1974","unstructured":"K. Heibig-Hansen and J. Krarup: Improvements of the Held-Karp algorithm for the symmetric TSP,Math. Programming,7 (1974), 87\u201396.","journal-title":"Math. Programming"},{"key":"BF01758756_CR22","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R. M. Karp: The traveling salesman problem and minimum spanning trees,Oper. Res.,18 (1970), 1138\u20131162.","journal-title":"Oper. Res."},{"key":"BF01758756_CR23","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R. M. Karp: The traveling salesman problem and minimum spanning trees, part II,Math. Programming,1 (1971), 6\u201325.","journal-title":"Math. Programming"},{"key":"BF01758756_CR24","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. E. Hopcroft","year":"1974","unstructured":"J. E. Hopcroft and R. E. Tarjan: Efficient planarity testing,J. Assoc. Comput. Math.,21 (1974), 549\u2013558.","journal-title":"J. Assoc. Comput. Math."},{"key":"BF01758756_CR25","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":"BF01758756_CR26","volume-title":"Steiner tree problems","author":"F. K. Hwang","year":"1989","unstructured":"F. K. Hwang and D. S. Richards: Steiner tree problems, Bell Laboratories, Murray Hill, NJ, Technical Memorandum 1989. To be published inNetworks."},{"issue":"4","key":"BF01758756_CR27","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,Discrete Comput. Geom.,3, 4 (1988), 367\u2013392.","journal-title":"Discrete Comput. Geom."},{"key":"BF01758756_CR28","doi-asserted-by":"crossref","first-page":"49","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,Discrete Math.,62 (1986), 49\u201357.","journal-title":"Discrete Math."},{"key":"BF01758756_CR29","volume-title":"The shortest network with a given topology","author":"F. K. Hwang","year":"1988","unstructured":"F. K. Hwang and J. F. Weng: The shortest network with a given topology, Bell Laboratories, Murray Hill, NJ, Technical Memorandum 1988."},{"issue":"1","key":"BF01758756_CR30","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(75)90055-1","volume":"4","author":"A. N. C. Kang","year":"1975","unstructured":"A. N. C. Kang and D. A. Ault: Some properties of the centroid of a free tree,Inform. Process. Lett,4, 1 (1975), 18\u201320.","journal-title":"Inform. Process. Lett"},{"key":"BF01758756_CR31","volume-title":"The C Programming Language","author":"B. Kernighan","year":"1978","unstructured":"B. Kernighan and D. Ritchie:The C Programming Language, Prentice-Hall, Englewood Cliffs, NJ, 1978."},{"issue":"1","key":"BF01758756_CR32","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J. R. Kruskal Jr.","year":"1956","unstructured":"J. R. Kruskal Jr.: On the shortest spanning subtree of a graph and the traveling salesman problem,Proc. Amer. Math. Soc.,7, 1 (1956), 48\u201350.","journal-title":"Proc. Amer. Math. Soc."},{"key":"BF01758756_CR33","first-page":"38","volume-title":"Methods of Nonlinear Programming","author":"H. W. Kuhn","year":"1967","unstructured":"H. W. Kuhn; On a pair of dual nonlinear programs, in:Methods of Nonlinear Programming, pp. 38\u201354, Ed. J. Abadie, North-Holland, Amsterdam, 1967."},{"key":"BF01758756_CR34","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/BF01584648","volume":"4","author":"H. W. Kuhn","year":"1973","unstructured":"H. W. Kuhn: A note on Fermat's problem,Math. Programming,4 (1973), 98\u2013107.","journal-title":"Math. Programming"},{"key":"BF01758756_CR35","volume-title":"The TST, A Guided Tour of Combinatoral Optimization","year":"1985","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Schmoys (eds.)The TST, A Guided Tour of Combinatoral Optimization, Wiley-Interscience, New York, 1985."},{"key":"BF01758756_CR36","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,Canad. Math. Bull.,4 (1961), 143\u2013148.","journal-title":"Canad. Math. Bull."},{"key":"BF01758756_CR37","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G. L. Miller","year":"1986","unstructured":"G. L. Miller: Finding small simple cycle separators for 2-connected planar graphs,J. Comput. System Sci.,32 (1986), 265\u2013179.","journal-title":"J. Comput. System Sci."},{"key":"BF01758756_CR38","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J. Milnor","year":"1964","unstructured":"J. Milnor: On the Betti numbers of real algebraic varieties,Amer. Math. Soc.,15 (1964), 275\u2013280.","journal-title":"Amer. Math. Soc."},{"key":"BF01758756_CR39","doi-asserted-by":"crossref","unstructured":"C. Monma, M. Paterson, S. Suri, and F. Yao: Computing Euclidean maximum spanning trees, ACM Computational Geometry Conference 1988, pp. 241\u2013251.","DOI":"10.1145\/73393.73418"},{"key":"BF01758756_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos:Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"BF01758756_CR41","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R. C. Prim","year":"1957","unstructured":"R. C. Prim: Shortest Connection Networks and Some Generalizations,Bell System Tech. J.,36 (1957), 1389\u20131401.","journal-title":"Bell System Tech. J."},{"key":"BF01758756_CR42","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":"BF01758756_CR43","unstructured":"P. W. Shor and W. D. Smith: Steiner hulls and \u03b8-hulls, manuscript, 1989."},{"key":"BF01758756_CR44","unstructured":"W. D. Smith: Studies in Discrete and Computational Geometry, Ph.D. Thesis, Program in Applied and Computational Mathematics, Princeton University, September 1988."},{"key":"BF01758756_CR45","unstructured":"D. Smith: Finding the optimum traveling salesman tour forN sites in the Euclidean plane in subexponential time and polynomial space,SIAM J. Comput., submitted."},{"key":"BF01758756_CR46","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: A O(N 1gN) algorithm for Steiner minimal tree problems in the Euclidean metric,Networks,11 (1981), 23\u201329.","journal-title":"Networks"},{"key":"BF01758756_CR47","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":"BF01758756_CR48","unstructured":"R. P. Stanley: The number of faces of simplicial poly topes and spheres, in: Discrete Geometry and Convexity,Proc. N. Y. Acad. Sci., (1986)."},{"key":"BF01758756_CR49","volume-title":"Data structures and network algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan: Data structures and network algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society of Industrial and Applied Mathematics, Philadelphia, PA, 1983."},{"key":"BF01758756_CR50","volume-title":"Theory of Equations","author":"J. V. Uspensky","year":"1948","unstructured":"J. V. Uspensky:Theory of Equations, McGraw-Hill, New York, 1948."},{"key":"BF01758756_CR51","volume-title":"Algebra","author":"B. L. Waerden van der","year":"1970","unstructured":"B. L. van der Waerden:Algebra, Ungar, New York, 1970."},{"key":"BF01758756_CR52","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","volume":"133","author":"H. E. Warren","year":"1968","unstructured":"H. E. Warren: Lower Bounds for approximation by nonlinear manifolds,Trans. Amer. Math. Soc., 133 (1968), 167\u2013178.","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF01758756_CR53","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"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758756.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758756\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T16:25:40Z","timestamp":1557332740000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":53,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01758756"],"URL":"https:\/\/doi.org\/10.1007\/bf01758756","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}