{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T15:51:07Z","timestamp":1784735467119,"version":"3.55.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1023\/a:1009758919736","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T22:50:41Z","timestamp":1040597441000},"page":"47-65","source":"Crossref","is-referenced-by-count":122,"title":["New Approximation Algorithms for the Steiner Tree Problems"],"prefix":"10.1007","volume":"1","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Zelikovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"127601_CR1","series-title":"Technical Report","volume-title":"An approximation algorithm for the Steiner tree problem","author":"P. Berman","year":"1991","unstructured":"Berman, P., and V. Ramaiyer. (1991). \u201cAn approximation algorithm for the Steiner tree problem.\u201d The Pennsylvania State University, PA, Technical Report #CS-91-05."},{"key":"127601_CR2","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P. Berman","year":"1994","unstructured":"Berman, P., and V. Ramaiyer. (1994). \u201cImproved approximations for the Steiner tree problem,\u201d J. of Algorithms vol. 17 pp. 381\u2013408.","journal-title":"J. of Algorithms"},{"key":"127601_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P., U. F\u00f6\u00dfmeier, M. Karpinski, M. Kaufmann, and A. Zelikovsky. (1994). \u201cApproaching the 5\/4-Approximations for Rectilinear Steiner Trees,\u201d LNCS vol. 855, Springer-Verlag, pp. 60\u201371, 1994.","DOI":"10.1007\/BFb0049397"},{"key":"127601_CR4","unstructured":"Bern, M., and D. Eppstein. (1995), \u201cApproximation Algorithms for Geometric Problems,\u201d in D. Hochbaum, (ed.), Approximation Algorithms for NP-Complete Problems, PWS Publications. (to appear)"},{"key":"127601_CR5","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern, M., and P. Plassmann. (1989). \u201cThe Steiner problems with edge lengths 1 and 2,\u201d lnform. Process. Lett. vol. 32 pp. 171\u2013176.","journal-title":"lnform. Process. Lett."},{"key":"127601_CR6","doi-asserted-by":"crossref","unstructured":"Borchers, A., and D. Du. (1995). \u201cThe k-Steiner Ratio in Graphs,\u201d Proc. 27th ACM STOC (1995), pp. 641\u2013649.","DOI":"10.1145\/225058.225282"},{"key":"127601_CR7","unstructured":"Du, D., Y. Zhang, and Q. Feng. (1991). \u201cOn better heuristic for Euclidean Steiner minimum trees,\u201d in Proc. 32nd IEEE Symp. on Found. of Comp. Science, pp. 43l\u2013439."},{"key":"127601_CR8","doi-asserted-by":"crossref","unstructured":"F\u00f6\u00dfmeier, U., M. Kaufmann, and A. Zelikovsky. (1993). \u201cFaster Approximation Algorithms for the Rectilinear Steiner Tree Problem,\u201d LNCS vol. 762, Springer-Verlag, pp. 533\u2013542.","DOI":"10.1007\/3-540-57568-5_285"},{"key":"127601_CR9","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"Garey, M. R., and D. S. Johnson. (1977). \u201cThe Rectilinear Steiner Problem is NP-Complete,\u201d SIAM J. Appl. Math. Vol. 32 pp. 826\u2013834.","journal-title":"SIAM J. Appl. Math."},{"key":"127601_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E. N. Gilbert","year":"1968","unstructured":"Gilbert, E. N., and H. O. Pollak. (1968). \u201cSteiner Minimal Trees,\u201d SIAM Appl. Math. vol. 16 pp. 1\u201329.","journal-title":"SIAM Appl. Math."},{"key":"127601_CR11","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F. K. Hwang","year":"1976","unstructured":"Hwang, F. K. (1976). \u201cOn Steiner Minimal Trees with Rectilinear Distance,\u201d SIAM J. Appl. Math. vol. 30 pp. 104\u2013114.","journal-title":"SIAM J. Appl. Math."},{"key":"127601_CR12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"F. K. Hwang","year":"1979","unstructured":"Hwang, F. K. (1979). \u201cAn o(n log n) algorithm for rectilinear minimum spanning trees,\u201d J. ACM vol. 26 pp. 177\u2013182.","journal-title":"J. ACM"},{"key":"127601_CR13","unstructured":"Hwang, F. K., D. Richards, and P. Winter. (1992). The Steiner Tree Problem, Annals of Disc. Math. vol. 53."},{"key":"127601_CR14","series-title":"Technical Report","volume-title":"1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems","author":"M. Karpinski","year":"1995","unstructured":"Karpinski, M., and A. Zelikovsky. (1995). \u201c1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems.\u201d International Computer Science Institute, Berkeley, CA, Technical Report TR-95010."},{"key":"127601_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2363-2","volume-title":"On optimal interconnections for VLSI","author":"A. B. Khang","year":"1995","unstructured":"Khang, A. B., and G. Robins, (1995). On optimal interconnections for VLSI, Kluwer Academic Publishers, Boston. MA."},{"key":"127601_CR16","unstructured":"Korte, B., H. J. Pr\u00f6mel, and A. Steger. (1990). \u201cSteiner Trees in VLSI-Layouts.\u201d in Korte et al. (eds.): Paths, Flows and VLSI-Layout, Springer."},{"key":"127601_CR17","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K. Mehlhorn","year":"1988","unstructured":"Mehlhorn, K. (1988), \u201cA faster approximation algorithm for the Steiner problem in graphs\u201dInf. Process. Lett. vol. 27 pp. 125\u2013128.","journal-title":"Inf. Process. Lett."},{"key":"127601_CR18","doi-asserted-by":"crossref","unstructured":"Salowe, J. S., and D. M. Warme. (1993). \u201cAn exact rectilinear Steiner tree algorithm,\u201d in Proc. of the lnt. Conf. on Comp. Design, pp. 472\u2013475.","DOI":"10.1109\/ICCD.1993.393331"},{"key":"127601_CR19","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"Takahashi, H., and A. Matsuyama. (1980), \u201cAn approximate solution for the Steiner problem in graphs.\u201d Math. Japonica vol. 24 pp. 573\u2013577.","journal-title":"Math. Japonica"},{"key":"127601_CR20","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A. Z. Zelikovsky","year":"1993","unstructured":"Zelikovsky, A. Z. (1993). \u201cAn 1l\/6-approximation Algorithm for the network Steiner Problem,\u201d Algorithmica vol. 9 pp. 463\u2013470.","journal-title":"Algorithmica"},{"key":"127601_CR21","first-page":"733","volume":"60","author":"A. Z. Zelikovsky","year":"1992","unstructured":"Zelikovsky, A. Z. (1992). \u201cAn 1l\/8-approximation Algorithm for the Steiner Problem on Networks with Rectilinear Distance,\u201d in Coll. Math. Soc. J. Bolyai vol. 60 pp. 733\u2013745.","journal-title":"Coll. Math. Soc. J. Bolyai"},{"key":"127601_CR22","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(93)90201-J","volume":"46","author":"A. Z. Zelikovsky","year":"1993","unstructured":"Zelikovsky, A. Z. (1993). \u201cA faster approximation algorithm for the Steiner Tree Problem in Graphs,\u201d lnf. Process. Lett. vol. 46 pp. 79\u201383.","journal-title":"lnf. Process. Lett."},{"key":"127601_CR23","unstructured":"Zelikovsky, A. Z. (1995). \u201cBetter approximation bounds for the network and Euclidean Steiner tree problems,\u201d Manuscript."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009758919736.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009758919736\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009758919736.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:02:08Z","timestamp":1751281328000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009758919736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["127601"],"URL":"https:\/\/doi.org\/10.1023\/a:1009758919736","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}