{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:11Z","timestamp":1725663311935},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_44","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:07:42Z","timestamp":1330204062000},"page":"529-540","source":"Crossref","is-referenced-by-count":3,"title":["On the complexity of single row routing problems"],"prefix":"10.1007","author":[{"given":"Adair","family":"Dingle","sequence":"first","affiliation":[]},{"given":"I. Hal","family":"Sudborough","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"issue":"12","key":"44_CR1","doi-asserted-by":"publisher","first-page":"1262","DOI":"10.1109\/TCS.1980.1084751","volume":"CAS-27","author":"L. Andersen","year":"1980","unstructured":"L. Andersen, \"On Single-Row Routing\", IEEE Transactions on Circuits and Systems, vol CAS-27, no. 12, Dec. 1980, pp. 1262\u20131263.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"44_CR2","unstructured":"P. Arnold, \"Complexity Results for Circuit Layout on Double-sided printed circuit boards\", Bachelor's thesis, Harvard University, 1982."},{"key":"44_CR3","unstructured":"A. Dingle and H. Sudborough, \"Single Row Routing Revisited\", manuscript, University of Texas at Dallas, January 1989."},{"key":"44_CR4","first-page":"199","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"M. Garey and S. Johnson, Computers and Intractability, San Francisco, CA: Freeman, 1979, p. 199."},{"issue":"3","key":"44_CR5","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1109\/43.3175","volume":"7","author":"T. F. Gonzalez","year":"1988","unstructured":"T. F. Gonzalez and S. Kurki-Gowdara, \"Minimization of the Number of Layers for Single Row Routing with Fixed Street Capacity\", IEEE Trans. Computer-Aided Design, vol 7, no. 3, March 1988, pp. 420\u2013424.","journal-title":"IEEE Trans. Computer-Aided Design"},{"issue":"3","key":"44_CR6","first-page":"235","volume":"CAD-3","author":"S. Han","year":"1984","unstructured":"S. Han, and S. Sahni, \"Single-Row Routing in Narrow Streets\", IEEE Transactions on Computer-Aided Design, vol CAD-3, no. 3, July 1984, pp. 235\u2013241.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"S. Han, and S. Sahni, \"Layering Algorithms for Single Row Routing\", in Proc. 22nd Design Automation Conf., 1985, pp. 516\u2013522.","DOI":"10.1145\/317825.317938"},{"issue":"6","key":"44_CR8","first-page":"209","volume":"CAS-26","author":"E. Kuh","year":"1979","unstructured":"E. Kuh, T. Kashiwabara, and T. Fujisawa, \"On Optimum Single-Row Routing\", IEEE Transactions on Circuits and Systems, vol CAS-26, no. 6, June 1979, pp. 209\u2013216.","journal-title":"IEEE Transactions on Circuits and Systems"},{"issue":"4","key":"44_CR9","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1109\/TCAD.1983.1270042","volume":"CAD-2","author":"M. Marek-Sadowska","year":"1983","unstructured":"M. Marek-Sadowska and T. Tarng, \"Single-Layer Routing for VLSI: Analysis and Algorithms\", IEEE Transactions on Computer-Aided Design, vol CAD-2, no. 4, Oct 1983, pp. 246\u2013259.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"issue":"3","key":"44_CR10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1109\/TC.1983.1676213","volume":"C-32","author":"R. Raghavan","year":"1983","unstructured":"R. Raghavan and S. Sahni, \"Single Row Routing\", IEEE Transactions on Computers, vol C-32, no. 3, March 1983, pp. 209\u2013220.","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"44_CR11","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1109\/TC.1984.1676428","volume":"C-33","author":"D. Richards","year":"1984","unstructured":"D. Richards, \"Complexity of Single-Layer Routing\", IEEE Trans. Computers, vol C-33, no. 3, March 1984, pp. 286\u2013288.","journal-title":"IEEE Trans. Computers"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"S. Sahni, A. Bhatt, and R. Raghavan, \"The complexity of design automation problems\", in Proc. 17th Design Automation Conf., 1980, pp. 402\u2013411.","DOI":"10.1145\/800139.804562"},{"issue":"12","key":"44_CR13","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1109\/TCS.1976.1084169","volume":"CAS-23","author":"B. Ting","year":"1976","unstructured":"B. Ting, E. S. Kuh, and I. Shirakawa, \"The Multilayer Routing Problem: Algorithms and Necessary and Sufficient Conditions for the Single-Row Single-Layer Case\", IEEE Transactions on Circuits and Systems, vol CAS-23, no. 12, Dec 1976, pp. 768\u2013778.","journal-title":"IEEE Transactions on Circuits and Systems"},{"issue":"9","key":"44_CR14","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1109\/TCS.1980.1084890","volume":"CAS-27","author":"S. Tsukiyama","year":"1980","unstructured":"S. Tsukiyama, E. S. Kuh, and I. Shirakawa, \"An Algorithm for Single-Row Routing with Prescribed Street Congestions\", IEEE Transactions on Circuits and Systems, vol CAS-27, no. 9, Sept. 1980, pp. 765\u2013772.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"44_CR15","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/TCAD.1983.1270018","volume":"CAD-2","author":"S. Tsukiyama","year":"1983","unstructured":"S. Tsukiyama, E. S. Kuh, and I. Shirakawa, \"On the layering problem on multilayer PWB wiring\", IEEE Trans. Computer-Aided Design, vol CAD-2, pp. 30\u201338, Jan 1983.","journal-title":"IEEE Trans. Computer-Aided Design"},{"issue":"3","key":"44_CR16","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1109\/TCAD.1984.1270073","volume":"CAD-3","author":"T. Tarng","year":"1984","unstructured":"T. Tarng, M. Marek-Sadowska, and E. Kuh, \"An Efficient Single-Row Routing Algorithm\", IEEE Transactions on Computer-Aided Design, vol CAD-3, no. 3, July 1984, pp. 178\u2013183.","journal-title":"IEEE Transactions on Computer-Aided Design"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:04:40Z","timestamp":1619571880000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}