{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:50Z","timestamp":1725663530599},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540564027"},{"type":"electronic","value":"9783540475545"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56402-0_42","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T06:09:04Z","timestamp":1330236544000},"page":"123-134","source":"Crossref","is-referenced-by-count":0,"title":["Minimum rectilinear steiner trees for intervals on two parallel lines"],"prefix":"10.1007","author":[{"given":"Edmund","family":"Ihler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"13_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:37\u201358, 1977.","journal-title":"Networks"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1002\/net.3230200407","volume":"20","author":"P. K. Agarwal","year":"1990","unstructured":"P. K. Agarwal and M.-T. Shing. Algorithms for special cases of rectilinear Steiner trees: 1. Points on the boundary of a rectilinear rectangle. Networks, 20:453\u2013485, 1990.","journal-title":"Networks"},{"issue":"4","key":"13_CR3","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. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 32(4):826\u2013834, 1977.","journal-title":"SIAM J. Appl. Math."},{"key":"13_CR4","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"issue":"2","key":"13_CR5","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(2):255\u2013265, 1966.","journal-title":"SIAM J. Appl. Math."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"E. Ihler. Bounds on the quality of approximate solutions to the Group Steiner Problem. In Graph-Theoretic Concepts in Computer Science, WG90, volume 484 of Lecture Notes in Computer Science, pages 109\u2013118. Springer, 1991.","DOI":"10.1007\/3-540-53832-1_36"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"E. Ihler. The complexity of approximating the Class Steiner Tree problem. In Graph-Theoretic Concepts in Computer Science, WG91, volume 570 of Lecture Notes in Computer Science, pages 85\u201396. Springer, 1992.","DOI":"10.1007\/3-540-55121-2_8"},{"key":"13_CR8","unstructured":"B. Korte, H. J. Pr\u00f6mel, and A. Steger. Steiner trees in VLSI-layout. In B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver, editors, Paths, Flows, and VLSI-Layout, pages 185\u2013214. Springer, 1990."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley & Sons, 1990.","DOI":"10.1007\/978-3-322-92106-2_3"},{"key":"13_CR10","unstructured":"T. Ottmann and P. Widmayer. Algorithmen und Datenstrukturen. BI-Wiss.-Verl., 1990."},{"key":"13_CR11","unstructured":"G. Reich. Shortest trees for intervals of points in the switchbox. Technical report, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1991."},{"key":"13_CR12","unstructured":"G. Reich and P. Widmayer. Approximate minimum spanning trees for vertex classes. Technical report, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1989."},{"key":"13_CR13","volume-title":"Technical report","author":"M. Sarrafzadeh","year":"1991","unstructured":"M. Sarrafzadeh and C.K. Wong. New directions in the rectilinear Steiner tree problem. Technical report, Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, and IBM Watson Research Center, Yorktown Heights, New York, 1991."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56402-0_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:03:43Z","timestamp":1605629023000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56402-0_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540564027","9783540475545"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-56402-0_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}