{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:43Z","timestamp":1725663703836},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540512950"},{"type":"electronic","value":"9783540461869"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51295-0_125","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:52:27Z","timestamp":1330203147000},"page":"155-170","source":"Crossref","is-referenced-by-count":1,"title":["A heuristic for channel routing"],"prefix":"10.1007","author":[{"given":"E.","family":"Lodi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TCAD.1985.1270096","volume":"CAD-4","author":"T. Szymanski","year":"1985","unstructured":"Szymanski T., \"Dogleg Channel Routing is NP-complete\", IEEE Trans. on CAD, CAD-4 (1985), 31\u201340.","journal-title":"IEEE Trans. on CAD"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Hashimoto, A. and J. Stevens, \"Wire Routing by Optimizing Channel Assignment within Large Apertures\", Proc. 8-th Design Automation Workshop, IEEE (1971), 214\u2013224.","DOI":"10.1145\/800158.805069"},{"key":"11_CR3","unstructured":"Kernighan, B., D. Schweikert, and G. Persky, \"An Optimal Channel-Routing Algorithm for Polycell Layouts of Integrated Circuits\", Proc. 10-th Design Automation Workshop, IEEE (1973), 50\u201359."},{"issue":"4","key":"11_CR4","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/MC.1974.6323494","volume":"7","author":"D. Hightower","year":"1974","unstructured":"Hightower, D., \"The Interconnection Problem: A Tutorial\", Computer 7, 4 (April 1974), 18\u201332.","journal-title":"Computer"},{"issue":"2","key":"11_CR5","first-page":"29","volume":"J59-A","author":"T. Asano","year":"1976","unstructured":"Asano, T., T. Kitchashi, and K. Tanaka, \"On a Method of Realizing Minimum-Width Wiring\", Electronics and Communications in Japan, J59-A, 2 (1976), 29\u201339.","journal-title":"Electronics and Communications in Japan"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Deutsch, D. N., \"A \u2018Dogleg \u2018Channel Router\", Proc. 19-th Design Automation Conference, IEEE (1976), 425\u2013433.","DOI":"10.1145\/800146.804843"},{"issue":"3","key":"11_CR7","first-page":"217","volume":"1","author":"G. Persky","year":"1977","unstructured":"Persky, G., D. Deutsch, and D. Schweikert, \"LTX \u2014 A Minicomputer-Based System for Automated LSI Layout\", Journal of Design Automation and Fault-Tolerant Computing, 1, 3 (May 1977), 217\u2013255.","journal-title":"Journal of Design Automation and Fault-Tolerant Computing"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Kawamoto, T. and Y. Kajitani, \"The Minimum Width Routing of a 2-Row 2-Layer Polycell-Layout\", Proc. 16-th Design Automation Conference, IEEE (1979), 290\u2013296.","DOI":"10.1109\/DAC.1979.1600121"},{"key":"11_CR9","unstructured":"Alford, S., \"DYCHAR: A Channel Router which uses dynamic channel assignment\", MIT Bachelor's thesis (May 1980)."},{"issue":"1","key":"11_CR10","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1109\/TCAD.1982.1269993","volume":"CAD-1","author":"T. Yoshimura","year":"1982","unstructured":"Yoshimura, T. and E. Kuh, \"Efficient Algorithms for Channel Routing\", IEEE Trans. on CAD, CAD-1, 1 (January 1982), 25\u201335.","journal-title":"IEEE Trans. on CAD"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Rivest, R. L. and C. M. Fiduccia, \"A \u2018Greedy\u2019 Channel Router\", Proc. 19-th IEEE Design Automation Conference, (1982), 418\u2013424.","DOI":"10.1109\/DAC.1982.1585533"},{"issue":"4","key":"11_CR12","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1109\/TCAD.1983.1270040","volume":"CAD-2","author":"M. Burstein","year":"1983","unstructured":"Burstein, M. and R. Pelavin, \"Hierarchical Channel Router\", IEEE Trans. on CAD, CAD-2, 4 (October 1983), 223\u2013234.","journal-title":"IEEE Trans. on CAD"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Rivest, R. L., A. E. Baratz and G. Miller, \"Provably Good Channel Routing Algorithms\", Proc. CMU Conference on VLSI Systems and Computations, (1981), 153\u2013159.","DOI":"10.1007\/978-3-642-68402-9_18"},{"issue":"5","key":"11_CR14","first-page":"427","volume":"33","author":"F. P. Preparata","year":"1984","unstructured":"Preparata, F. P. and W. Lipski, \"Optimal Three-Layer Channel Routing\", IEEE Trans. on CAD, 33, 5 (May 1984), 427\u2013437.","journal-title":"IEEE Trans. on CAD"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Brown, D. and R. L. Rivest, \"New Lower Bounds on Channel Width\", Proc. CMU Conference on VLSI Systems and Computations (Computer Science Press 1981), 178\u2013185.","DOI":"10.1007\/978-3-642-68402-9_20"},{"key":"11_CR16","first-page":"205","volume":"2","author":"B. S. Baker","year":"1984","unstructured":"Baker, B. S., S. N. Bhatt and T. Leighton, \"An Approximation Algorithm for Manhattan Routing\", Advances in Computing Research, 2 (1984), 205\u2013229.","journal-title":"Advances in Computing Research"},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0377-2217(86)90218-3","volume":"23","author":"P. Carraresi","year":"1986","unstructured":"Carraresi, P. and C. Sodini, \"An efficient algorithm for the bipartite matching problem\", EJOR, 23 (1986), 86\u201393.","journal-title":"EJOR"},{"key":"11_CR18","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"j. Edmonds","year":"1972","unstructured":"Edmonds, j. and R. Karp. \"Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems\", Journal of ACM, 19 (1972), 248\u2013264.","journal-title":"Journal of ACM"},{"key":"11_CR19","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"Fredman, M. and R. Tarjan, \"Fibonacci Heaps and their uses in Improved Network Optimization Algorithms\", Journal of ACM, 34 (1987), 596\u2013615.","journal-title":"Journal of ACM"}],"container-title":["Lecture Notes in Computer Science","Foundations of Data Organization and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51295-0_125.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:20:49Z","timestamp":1605648049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51295-0_125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540512950","9783540461869"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-51295-0_125","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}