{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:06Z","timestamp":1725664926234},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540625599"},{"type":"electronic","value":"9783540680727"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62559-3_17","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:41:05Z","timestamp":1330278065000},"page":"196-210","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Switchbox routing in VLSI design: Closing the complexity gap"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Hartmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus W.","family":"Sch\u00e4ffter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1006\/jagm.1993.1041","volume":"15","author":"M. Formann","year":"1993","unstructured":"M. Formann, D. Wagner, and F. Wagner. Routing through a dense channel with minimum total wire length. Journal of Algorithms, 15:267\u2013283, 1993.","journal-title":"Journal of Algorithms"},{"key":"17_CR2","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979."},{"key":"17_CR3","unstructured":"M. Gr\u00f6tschel, A. Martin, and R. Weismantel. Routing in grid graphs by cutting planes. In G. Rinaldi and L. Wolsey, editors, Third IPCO Conference, pages 447\u2013461, 1993."},{"key":"17_CR4","volume-title":"Fachbereich Mathematik","author":"S. Hartmann","year":"1996","unstructured":"S. Hartmann. Channel routing with 4-terminal nets is NP-complete. Preprint, Fachbereich Mathematik, Technische Universit\u00e4t Berlin, Berlin, Germany, 1996."},{"key":"17_CR5","unstructured":"B. Korte, H.-J. Pr\u00f6mel, and A. Steger. Steiner trees in VLSI-layout. In B. Korte, L. Lovasz, H. J. Pr\u00f6mel, and A. Schrijver, editors, Paths, Flows and VLSI-Layout, pages 185\u2013214. Springer Verlag, 1990."},{"key":"17_CR6","first-page":"129","volume-title":"Advances in Computing Research, Vol. 2 VLSI theory","author":"M. R. Kramer","year":"1984","unstructured":"M. R. Kramer and J. van Leeuwen. The complexity of wire routing and finding minimum area layouts for arbitrary VLSI circuits. In F. P. Preparata, editor, Advances in Computing Research, Vol. 2 VLSI theory, pages 129\u2013146. JAI Press, Reading, MA, 1984."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Th. Lengauer. Combinatorical Algorithms for Integrated Circuit Layout. Teubner\/Wiley&Sons, 1990.","DOI":"10.1007\/978-3-322-92106-2_3"},{"key":"17_CR8","unstructured":"M. Middendorf. Manhattan channel routing is \n                  \n                    \n                  \n                  \n$$\\mathcal{N}\\mathcal{P}$$\n\n                -complete under truly restricted settings. Preprint, Universit\u00e4t Karlruhe, 1993. To appear in the Chicago Journal of Theoretical Computer Science."},{"issue":"1","key":"17_CR9","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/4904.4994","volume":"33","author":"K. Mehlhorn","year":"1986","unstructured":"K. Mehlhorn and F. P. Preparata. Routing through a rectangle. Journal of the Association for Computing Machinery, 33(1):60\u201385, 1986.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0167-9260(92)90017-S","volume":"13","author":"M. Marek-Sadowska","year":"1992","unstructured":"M. Marek-Sadowska. Switch box routing: a retrospective. Integration, the VLSI Journal, 13:39\u201365, 1992.","journal-title":"Integration, the VLSI Journal"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"R. H. M\u00f6hring, D. Wagner, and F. Wagner. Network Routing, chapter VLSI Network Design, pages 625\u2013712. Handbooks in Operations Research and Management Science. Elsevier, 1995.","DOI":"10.1016\/S0927-0507(05)80112-4"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"H. Okamura and P. D. Seymour. Multicommodity flows in planar graphs. Journal of Computer Theory, pages 75\u201381, 1981.","DOI":"10.1016\/S0095-8956(81)80012-3"},{"issue":"4","key":"17_CR13","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1109\/TCAD.1987.1270298","volume":"6","author":"M. Sarrafzadeh","year":"1987","unstructured":"M. Sarrafzadeh. Channel-routing problem in the knock-knee mode is NP-complete. IEEE Transaction on Computer-Aided Design, 6(4):503\u2013506, 1987.","journal-title":"IEEE Transaction on Computer-Aided Design"},{"issue":"1","key":"17_CR14","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TCAD.1985.1270096","volume":"4","author":"T. G. Szymanski","year":"1985","unstructured":"T. G. Szymanski. Dogleg channel-routing is NP-complete. IEEE Transaction on Computer-Aided Design, 4(1):31\u201341, 1985.","journal-title":"IEEE Transaction on Computer-Aided Design"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62559-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:29:38Z","timestamp":1578508178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62559-3_17"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540625599","9783540680727"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-62559-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"3 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}