{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T23:49:50Z","timestamp":1773964190065,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1992,5,1]],"date-time":"1992-05-01T00:00:00Z","timestamp":704678400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1992,5]]},"DOI":"10.1007\/bf01581080","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T05:52:15Z","timestamp":1114667535000},"page":"193-202","source":"Crossref","is-referenced-by-count":13,"title":["On better heuristics for Steiner minimum trees"],"prefix":"10.1007","volume":"57","author":[{"given":"Ding-Zhu","family":"Du","sequence":"first","affiliation":[]},{"given":"Yanjun","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","unstructured":"P. Berman and V. Ramaiye, \u201cAn approximation algorithm for the Steiner tree problem,\u201d manuscript."},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"M. Bern, \u201cTwo probabilistic results on rectilinear Steiner trees,\u201dProceedings of the 18th Annual ACM Symposium on Theory of Computing (1986) 433\u2013441.","DOI":"10.1145\/12130.12175"},{"key":"CR3","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, \u201cA new bound for euclidean Steiner minimum trees,\u201dAnnual New York Academy of Sciences 440 (1985) 328\u2013346.","journal-title":"Annual New York Academy of Sciences"},{"key":"CR4","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, \u201cA lower bound for the Steiner tree problem,\u201dSIAM Journal of Applied Mathematics 34 (1978) 27\u201336.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR5","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, \u201cA new bound for the Steiner ratio,\u201dTransactions of American Mathematical Society 278 (1983) 137\u2013148.","journal-title":"Transactions of American Mathematical Society"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"D.-Z. Du and F.K. Hwang, \u201cAn approach for proving lower bounds: solution of Gilbert\u2014Pollak's conjecture on Steiner ratio,\u201dProceedings of the 31st Annual Symposium on Foundations of Computer Science (1990) 76\u201385.","DOI":"10.1109\/FSCS.1990.89526"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L.R. Foulds","year":"1982","unstructured":"L.R. Foulds and R.L. Graham, \u201cThe Steiner problem in phylogeny is NP-complete,\u201dAdvances in Applied Mathematics 3 (1982) 43\u201349.","journal-title":"Advances in Applied Mathematics"},{"key":"CR8","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, \u201cThe complexity of computing Steiner minimal trees,\u201dSIAM Journal of Applied Mathematics 32 (1977) 835\u2013859.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"M.R. Garey and D.S. Johnson, \u201cThe rectilinear Steiner tree problem is NP-complete,\u201dSIAM Journal of Applied Mathematics 32 (1977) 826\u2013834.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR10","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, \u201cSteiner minimal trees,\u201dSIAM Journal of Applied Mathematics 16 (1968) 1\u201329.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR11","first-page":"177","volume":"4","author":"R.L. Graham","year":"1976","unstructured":"R.L. Graham and F.K. Hwang, \u201cRemarks on Steiner minimal trees,\u201dBulletin of Institute of Mathematics, Academia Sinica 4 (1976) 177\u2013182.","journal-title":"Bulletin of Institute of Mathematics, Academia Sinica"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F.K. Hwang","year":"1976","unstructured":"F.K. Hwang, \u201cOn Steiner minimal trees with rectilinear distance,\u201dSIAM Journal of Applied Mathematics 30 (1976) 104\u2013114.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF01840406","volume":"5","author":"F.K. Hwang","year":"1990","unstructured":"F.K. Hwang and Y.C. Yao, \u201cComments on Bern's probabilistic results on rectilinear Steiner trees,\u201dAlgorithmica 5 (1990) 591\u2013598.","journal-title":"Algorithmica"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computation","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems,\u201d in: R.E. Miller and J.W. Tatcher, ed.,Complexity of Computer Computation (Plenum Press, New York, 1972) pp. 85\u2013103."},{"key":"CR15","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, \u201cSome remarks on the Steiner problem,\u201dJournal of Combinatorial Theory Series A 24 (1978) 278\u2013295.","journal-title":"Journal of Combinatorial Theory Series A"},{"key":"CR16","unstructured":"J.H. Rubinstein and D.A. Thomas, \u201cThe Steiner ratio conjecture for six points,\u201d to appear in:Journal of Combinatoria Theory Series A."},{"key":"CR17","unstructured":"A.Z. Zelikovsky, \u201cThe 11\/6-approximation algorithm for the Steiner problem on networks,\u201d manuscript."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581080.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01581080\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:12:14Z","timestamp":1556881934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01581080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":17,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["BF01581080"],"URL":"https:\/\/doi.org\/10.1007\/bf01581080","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}