{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:27:18Z","timestamp":1751282838879,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540584346"},{"type":"electronic","value":"9783540487944"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049397","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:42:35Z","timestamp":1141670555000},"page":"60-71","source":"Crossref","is-referenced-by-count":7,"title":["Approaching the 5\/4 \u2014 approximation for rectilinear Steiner trees"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[]},{"given":"Ulrich","family":"F\u00f6\u00dfmeier","sequence":"additional","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Zelikovsky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"7_CR1","unstructured":"P. Berman, V. Ramaiyer. Improved approximations for the Steiner tree problem. In Proc. of 3d ACM-SIAM Symp. on Discrete Algorithms, 325\u2013334, 1992."},{"key":"7_CR2","unstructured":"P. Berman, U. F\u00f6\u00dfmeier, M. Karpinski, M. Kaufmann, A. Zelikovsky. Approaching the 5\/4-Approximations for Rectilinear Steiner Trees. Techn. Rep. WSI-94-6, T\u00fcbingen."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"D. Du, Y. Zhang, Q. Feng. On better heuristic for Euclidean Steiner minimum trees. 32nd IEEE Symp. on Found, of Comp. Science, 431\u2013439, 1991.","DOI":"10.1109\/SFCS.1991.185402"},{"key":"7_CR4","unstructured":"D. Eppstein, et al. Maintaining of a Minimum Spanning Forest in a Dynamic Planar Graph. Proceedings, 1st ACM-SIAM Symp. on Discrete Algorithms, 1\u201311, 1990."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"U. F\u00f6\u00dfmeier, M. Kaufmann, A. Zelikovsky. Faster Approximation Algorithms for the Rectilinear Steiner Tree Problem. LNCS 762, 533\u2013542, 1993.","DOI":"10.1007\/3-540-57568-5_285"},{"key":"7_CR6","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. Frederickson","year":"1985","unstructured":"G. Frederickson. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications. SIAM J. Comp., 14, 781\u2013789, 1985.","journal-title":"SIAM J. Comp."},{"key":"7_CR7","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"M. R. Garey, D. S. Johnson. The Rectilinear Steiner Problem is NP-Complete. SIAM J. Appl. Math., 32, 826\u2013834, 1977.","journal-title":"SIAM J. Appl. Math."},{"key":"7_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E. N. Gilbert","year":"1968","unstructured":"E. N. Gilbert, H. O. Pollak. Steiner Minimal Trees. SIAM Appl. Math., 16, 1\u201329, 1968.","journal-title":"SIAM Appl. Math."},{"key":"7_CR9","doi-asserted-by":"publisher","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, 255\u2013265, 1966.","journal-title":"SIAM J. Appl. Math."},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F. K. Hwang","year":"1976","unstructured":"F. K. Hwang. On Steiner Minimal Trees with Rectilinear Distance. SIAM J. Appl. Math., 30, 104\u2013114, 1976.","journal-title":"SIAM J. Appl. Math."},{"key":"7_CR11","unstructured":"F. K. Hwang, D. S. Richards, P. Winter. The Steiner Tree Problem. Annals of Disc. Math. 53, 1992."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In Miller and Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 85\u2013103, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"7_CR13","unstructured":"B.Korte, H.J.Pr\u00f6mel, A.Steger. Steiner Trees in VLSI-Layouts. In Korte et al.: Paths, Flows and VLSI-Layout, Springer, 1990."},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Th. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley, 1990.","DOI":"10.1007\/978-3-322-92106-2_3"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01553886","volume":"4","author":"D. Richards","year":"1989","unstructured":"D. Richards. Fast Heuristic Algorithms for Rectilinear Steiner Trees. Algorithmica, 4, 191\u2013207, 1989.","journal-title":"Algorithmica"},{"key":"7_CR16","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"H. Takahashi, A. Matsuyama. An approximate solution for the Steiner problem in graphs. Math. Japonica, 24: 573\u2013577, 1980.","journal-title":"Math. Japonica"},{"key":"7_CR17","first-page":"733","volume":"60","author":"A. Z. Zelikovsky","year":"1992","unstructured":"A. Z. Zelikovsky. An 11\/8-approximation Algorithm for the Steiner Problem on Networks with Rectilinear Distance. In Coll. Math. Soc. J. Bolyai 60: 733\u2013745, 1992.","journal-title":"Coll. Math. Soc. J. Bolyai"},{"key":"7_CR18","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(93)90201-J","volume":"46","author":"A.Z. Zelikovsky","year":"1993","unstructured":"A.Z. Zelikovsky. A Faster Approximation Algorithm for the Steiner Tree Problem in Graphs. Inf. Process. Lett. 46: 79\u201383, 1993.","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T23:00:16Z","timestamp":1736290816000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0049397","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}