{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:25:41Z","timestamp":1750307141170,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,3,27]],"date-time":"2011-03-27T00:00:00Z","timestamp":1301184000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,3,27]]},"DOI":"10.1145\/1960397.1960404","type":"proceedings-article","created":{"date-parts":[[2011,3,22]],"date-time":"2011-03-22T12:25:29Z","timestamp":1300796729000},"page":"13-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On old and new routing problems"],"prefix":"10.1145","author":[{"given":"Malgorzata","family":"Marek-Sadowska","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3,27]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"296","volume-title":"Symp. on Circuits and Systems","author":"So H. C.","unstructured":"H. C. So , \"Some theoretical results on the routing of multilayer printed-wiring boards\",\"in Proc. I974 IEEE Int . Symp. on Circuits and Systems , pp. 296 -- 303 . H. C. So, \"Some theoretical results on the routing of multilayer printed-wiring boards\",\"in Proc. I974 IEEE Int. Symp. on Circuits and Systems, pp. 296--303."},{"key":"e_1_3_2_1_2_1","first-page":"23","article-title":"The multilayer routing problem: Algorithms and necessary and sufficient conditions for the single-row, single-layer case","author":"Ting B. S.","year":"1976","unstructured":"B. S. 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 Trans. Circuits Syst. , vol. C AS 23 , pp. 768--778, Dec. 1976 . B. S. 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 Trans. Circuits Syst., vol. CAS 23, pp. 768--778, Dec. 1976.","journal-title":"\"IEEE Trans. Circuits Syst."},{"volume-title":"1978 IEEE Int. Symp. on Circuits and Systems.","author":"Ting B. S.","key":"e_1_3_2_1_3_1","unstructured":"B. S. Ting and E. S. Kuh , \" An approach to the routing of multilayer printed circuit boards\",\"in Proc . 1978 IEEE Int. Symp. on Circuits and Systems. B. S. Ting and E. S. Kuh, \"An approach to the routing of multilayer printed circuit boards\",\"in Proc. 1978 IEEE Int. Symp. on Circuits and Systems."},{"issue":"6","key":"e_1_3_2_1_4_1","article-title":"On Optimum Single-Row Routing","volume":"26","author":"Kuh E. S.","year":"1979","unstructured":"E. S. Kuh , T. Kashiwabara , and T. Fujisawa , \" On Optimum Single-Row Routing \", \"IEEE Transactions on Circuits and Systems , vol. 26 , no. 6 , June 1979 . E. S. Kuh, T. Kashiwabara, and T. Fujisawa, \"On Optimum Single-Row Routing\",\"IEEE Transactions on Circuits and Systems, vol. 26, no. 6, June 1979.","journal-title":"\"IEEE Transactions on Circuits and Systems"},{"key":"e_1_3_2_1_5_1","first-page":"21","author":"Tsukyama S.","year":"1980","unstructured":"S. Tsukyama , E. S. Kuh , and I. Shirakawa ,\"\"An Algorithm for Single-Row Routing with Prescribed Street Congestions\", \"IEEE Transactions on Circuits and Systems , vol. C AS- 21 , no. 9, September 1980 , pp. 765--772. S. Tsukyama, E. S. Kuh, and I. Shirakawa,\"\"An Algorithm for Single-Row Routing with Prescribed Street Congestions\",\"IEEE Transactions on Circuits and Systems, vol. CAS-21, no. 9, September 1980, pp. 765--772.","journal-title":"\"IEEE Transactions on Circuits and Systems"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676213"},{"key":"e_1_3_2_1_7_1","first-page":"1437","volume-title":"Int. Symp. On Circuits and Systems","author":"Bhattacharya B. B.","year":"1983","unstructured":"B. B. Bhattacharya , J. S. Deogun , N. A. Sherwani , \" A Graph Theoretic Approach to Single Row Routing Problems\",\"Proc. Int. Symp. On Circuits and Systems , 1983 , pp. 1437 -- 1440 . B. B. Bhattacharya, J. S. Deogun, N. A. Sherwani, \"A Graph Theoretic Approach to Single Row Routing Problems\",\"Proc. Int. Symp. On Circuits and Systems, 1983, pp. 1437--1440."},{"key":"e_1_3_2_1_8_1","first-page":"565","article-title":"New Lower Bounds for Single Row Routing Problems","author":"Sherwani N. A.","year":"1989","unstructured":"N. A. Sherwani and J. S. Deogun , \" New Lower Bounds for Single Row Routing Problems \", \"Proc. of the 32nd Midwest Symposium on Circuits and Systems , 1989 , pp. 565 -- 568 . N. A. Sherwani and J. S. Deogun, \"New Lower Bounds for Single Row Routing Problems\",\"Proc. of the 32nd Midwest Symposium on Circuits and Systems, 1989, pp. 565--568.","journal-title":"\"Proc. of the 32nd Midwest Symposium on Circuits and Systems"},{"key":"e_1_3_2_1_9_1","first-page":"823","article-title":"Optimal algorithms for restricted single row routing problems","author":"Hossain M.","year":"1991","unstructured":"M. Hossain , N. A. Sherwani and J. S. Deogun , \" Optimal algorithms for restricted single row routing problems \", \"Proc. of the 34th Midwest Symposium on Circuits and Systems , 1991 , pp. 823 -- 826 . M. Hossain, N. A. Sherwani and J. S. Deogun, \"Optimal algorithms for restricted single row routing problems\",\"Proc. of the 34th Midwest Symposium on Circuits and Systems, 1991, pp. 823--826.","journal-title":"\"Proc. of the 34th Midwest Symposium on Circuits and Systems"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270263"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/81.139291"},{"key":"e_1_3_2_1_12_1","first-page":"5","article-title":"The Complexity of Single Row Routing","volume":"31","author":"Raghavan R.","year":"1984","unstructured":"R. Raghavan and S. Sahni , \" The Complexity of Single Row Routing \", \"IEEE Transactions on Circuits and Systems\" , vol. 31 . no. 5 , 1984 , pp. 462--472. R. Raghavan and S. Sahni, \"The Complexity of Single Row Routing\",\"IEEE Transactions on Circuits and Systems\", vol. 31. no.5, 1984, pp. 462--472.","journal-title":"\"IEEE Transactions on Circuits and Systems\""},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1984.1270073"},{"key":"e_1_3_2_1_14_1","first-page":"123","volume-title":"The Single Row Routing Problem Revisited: A Solution Based on Genetic Algorithms\",\"VLSI Design","author":"Zomaya A. Y.","year":"2002","unstructured":"A. Y. Zomaya , R. Karpin and S. Olariu , \" The Single Row Routing Problem Revisited: A Solution Based on Genetic Algorithms\",\"VLSI Design , 2002 vol. 14 (2), pp. 123 -- 141 . A. Y. Zomaya, R. Karpin and S. Olariu, \"The Single Row Routing Problem Revisited: A Solution Based on Genetic Algorithms\",\"VLSI Design, 2002 vol. 14 (2), pp. 123--141."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-006-0005-4"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITNG.2009.316"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800158.805069"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800146.804843"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800158.805069"},{"key":"e_1_3_2_1_21_1","first-page":"3","article-title":"General Channel-Routing Algorithm","volume":"130","author":"Marek-Sadowska M.","year":"1983","unstructured":"M. Marek-Sadowska and E.S. Kuh , \" General Channel-Routing Algorithm \", \"IEE Proceedings , Vol. 130 , Ft. G, No. 3 , June 1983 , pp. 83--88. M. Marek-Sadowska and E.S. Kuh, \"General Channel-Routing Algorithm\",\"IEE Proceedings, Vol. 130, Ft. G, No. 3, June 1983, pp. 83--88.","journal-title":"\"IEE Proceedings"},{"key":"e_1_3_2_1_22_1","first-page":"5","article-title":"Glitter: A Gridless Variable-Width Channel Router","author":"Chen H.H.","year":"1986","unstructured":"H.H. Chen and E.S. Kuh , \" Glitter: A Gridless Variable-Width Channel Router \", \"IEEE Transactions on Computer-Aided Design , vol. C AD- 5 , no. 4, October 1986 , pp. 459--465. H.H. Chen and E.S. Kuh, \"Glitter: A Gridless Variable-Width Channel Router\",\"IEEE Transactions on Computer-Aided Design, vol. CAD-5, no. 4, October 1986, pp. 459--465.","journal-title":"\"IEEE Transactions on Computer-Aided Design"},{"key":"e_1_3_2_1_23_1","first-page":"309","volume-title":"Proc. International Conf. on Circuits and Systems","author":"Kato H.","year":"1974","unstructured":"H. Kato , H. Kawanishi , S. Goto , T. Oyamada , and K. Kani , \" On automated wire routing for building-block MOS LSI \", Proc. International Conf. on Circuits and Systems , 1974 , pp. 309 -- 312 . H. Kato, H. Kawanishi, S. Goto, T. Oyamada, and K. Kani, \"On automated wire routing for building-block MOS LSI\", Proc. International Conf. on Circuits and Systems, 1974, pp. 309--312."},{"key":"e_1_3_2_1_24_1","first-page":"2","author":"Kimura S.","unstructured":"S. Kimura , N. Kubo , T. Chiba ,and I. Nishioka ,\"\"An automatic routing scheme for general cell LSI\", \"IEEE Trans. Computer Aided Design , vol. C AD- 2 , no. 4, pp. 285--292, Oct. 1983. S.Kimura, N.Kubo,T.Chiba,and I.Nishioka,\"\"An automatic routing scheme for general cell LSI\",\"IEEE Trans. Computer Aided Design, vol. CAD-2, no. 4, pp. 285--292, Oct. 1983.","journal-title":"\"IEEE Trans. Computer Aided Design"},{"key":"e_1_3_2_1_25_1","first-page":"667","volume-title":"27st DAC","author":"Kozawa T.","year":"1984","unstructured":"T. Kozawa , C. Miura , and H. Terai , \" Combine and Top Down Block Placement Algorithm for Hierarchical Logic VLSl Layout\",\"Proc . 27st DAC , 1984 , pp. 667 -- 669 . T. Kozawa, C. Miura, and H. Terai, \"Combine and Top Down Block Placement Algorithm for Hierarchical Logic VLSl Layout\",\"Proc. 27st DAC, 1984, pp. 667--669."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/37888.37945"},{"key":"e_1_3_2_1_27_1","first-page":"52","volume-title":"Int. Conf. on Computer Aided Design","author":"Dai W. W.-M.","year":"1990","unstructured":"W. W.-M. Dai , R. Kong , J. Jue and M. Sato , \" Rubber Band Routing and Dynamic Data Representation\",\"Proc . Int. Conf. on Computer Aided Design , 1990 , pp. 52 -- 55 . W. W.-M. Dai, R. Kong, J. Jue and M. Sato, \"Rubber Band Routing and Dynamic Data Representation\",\"Proc. Int. Conf. on Computer Aided Design, 1990, pp. 52--55."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.245960"},{"key":"e_1_3_2_1_29_1","first-page":"700","volume-title":"Int. Conf. on Computer Aided Design","author":"Su J. Z.","year":"1997","unstructured":"J. Z. Su and W. W. Dai , \" Post-Route Optimization for Improved Yield Using a Rubber-Band Wiring Model\",\"Proc . Int. Conf. on Computer Aided Design , 1997 , pp. 700 -- 706 . J. Z. Su and W. W. Dai, \"Post-Route Optimization for Improved Yield Using a Rubber-Band Wiring Model\",\"Proc. Int. Conf. on Computer Aided Design, 1997, pp.700--706."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800160.805107"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800139.804592"},{"key":"e_1_3_2_1_32_1","first-page":"2","article-title":"An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints","author":"Liao Y.Z.","year":"1983","unstructured":"Y.Z. Liao and C.K. Wong , \" An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints \", \"IEEE Transactions on Computer-Aided Design , vol. C AD- 2 , no 2, April 1983 , pp. 62--69. Y.Z. Liao and C.K. Wong, \"An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints\",\"IEEE Transactions on Computer-Aided Design, vol. CAD-2, no 2, April 1983, pp. 62--69.","journal-title":"\"IEEE Transactions on Computer-Aided Design"},{"key":"e_1_3_2_1_33_1","first-page":"223","volume-title":"Int. Conf. on Computer Aided Design\"","author":"Deutsch D. N.","year":"1985","unstructured":"D. N. Deutsch , \" Compacted Channel Routing ,\"\"Proc. Int. Conf. on Computer Aided Design\" , November 1985 , pp. 223 -- 225 . D. N. Deutsch, \"Compacted Channel Routing,\"\"Proc. Int. Conf. on Computer Aided Design\", November 1985, pp. 223--225."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.1985.294681"},{"key":"e_1_3_2_1_35_1","first-page":"697","volume-title":"International Conference on Computer Aided Design","author":"Chaudhary K.","year":"1993","unstructured":"K. Chaudhary , A. Onozawa and E.S. Kuh , \" A Spacing Algorithm for Performance Enhancement and Cross-talk Reduction\",\"Proc . International Conference on Computer Aided Design , 1993 , pp 697 -- 702 . K. Chaudhary, A. Onozawa and E.S. Kuh, \"A Spacing Algorithm for Performance Enhancement and Cross-talk Reduction\",\"Proc. International Conference on Computer Aided Design, 1993, pp 697--702."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.387731"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/244522.244575"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.664224"},{"key":"e_1_3_2_1_39_1","first-page":"74","volume-title":"International Conference on Computer Aided Design","author":"Xue T.","year":"1995","unstructured":"T. Xue and E.S. Kuh , \" Post Routing Performance Optimization via Tapered Link Insertion\",\"Proc . International Conference on Computer Aided Design , 1995 , pp. 74 -- 79 . T. Xue and E.S. Kuh, \"Post Routing Performance Optimization via Tapered Link Insertion\",\"Proc. International Conference on Computer Aided Design, 1995, pp. 74--79."},{"key":"e_1_3_2_1_40_1","first-page":"575","article-title":"Post Routing Performance Optimization via Multi-Link Insertion and Non-Uniform Wiresizing","author":"Xue T.","year":"1995","unstructured":"T. Xue and E.S. Kuh , \" Post Routing Performance Optimization via Multi-Link Insertion and Non-Uniform Wiresizing \", \"Proc. of the Conference on European Design Automation , 1995 , pp. 575 -- 580 . T. Xue and E.S. Kuh, \"Post Routing Performance Optimization via Multi-Link Insertion and Non-Uniform Wiresizing\",\"Proc. of the Conference on European Design Automation, 1995, pp. 575--580.","journal-title":"\"Proc. of the Conference on European Design Automation"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996574"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISQED.2006.66"},{"key":"e_1_3_2_1_43_1","first-page":"524","volume-title":"29th Design Automation Conference","author":"Mitsuhashi T.","year":"1992","unstructured":"T. Mitsuhashi and E. S. Kuh , \" Power and Ground Network Topology Optimization\",\"Proc . 29th Design Automation Conference , 1992 , pp. 524 -- 529 . T. Mitsuhashi and E. S. Kuh, \"Power and Ground Network Topology Optimization\",\"Proc. 29th Design Automation Conference, 1992, pp. 524--529."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2009.2036267"},{"volume-title":"A Survey on Multi-net Global Routing for Integrated Circuits. Integration, the VLSI Journal","author":"Hu J.","key":"e_1_3_2_1_45_1","unstructured":"J. Hu and S. Sapatnekar . A Survey on Multi-net Global Routing for Integrated Circuits. Integration, the VLSI Journal , vol. 31 , no. 1, pp. 1--49, 2002. J. Hu and S. Sapatnekar. A Survey on Multi-net Global Routing for Integrated Circuits. Integration, the VLSI Journal, vol. 31, no. 1, pp. 1--49, 2002."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907003"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497561.1497575"},{"key":"e_1_3_2_1_48_1","volume-title":"Proc. International Conference on Computer Aided Design","author":"Cho M.","year":"2008","unstructured":"M. Cho , Y. Ban , and D.Z. Pan , \" Double Patterning Technology Friendly Detailed Routing \", Proc. International Conference on Computer Aided Design , 2008 , 506--511. M. Cho, Y.Ban, and D.Z. Pan, \"Double Patterning Technology Friendly Detailed Routing\", Proc. International Conference on Computer Aided Design, 2008, 506--511."},{"key":"e_1_3_2_1_49_1","first-page":"637","volume-title":"Asia and South Pacific Design Automation Conf.","author":"Yang J.-S.","year":"2010","unstructured":"J.-S. Yang , K. Lu , M. Cho , K. Yuan , and D. Z. Pan , \" A New Graph Theoretic\", Multi-Objective Layout Decomposition Framework for Double Patterning Lithography,\" Proc . Asia and South Pacific Design Automation Conf. , 2010 , pp. 637 -- 644 . J.-S. Yang, K. Lu, M. Cho, K. Yuan, and D. Z. Pan, \"A New Graph Theoretic\", Multi-Objective Layout Decomposition Framework for Double Patterning Lithography,\" Proc. Asia and South Pacific Design Automation Conf., 2010, pp. 637--644."},{"key":"e_1_3_2_1_50_1","first-page":"06","article-title":"Integrated Circuit Fabrication and Associated Methods, Devices and Systems","volume":"06","author":"Maly W.","unstructured":"W. Maly , \" Integrated Circuit Fabrication and Associated Methods, Devices and Systems \", \"U.S. Non-Provisional Patent Application Serial Number Carnegie Mellon University Docket 06-091 ; DMC Docket 06 - 001 PCTCarnegie Mellon University. W. Maly, \"Integrated Circuit Fabrication and Associated Methods, Devices and Systems\",\"U.S. Non-Provisional Patent Application Serial Number Carnegie Mellon University Docket 06-091; DMC Docket 06-001PCTCarnegie Mellon University.","journal-title":"\"U.S. Non-Provisional Patent Application Serial Number Carnegie Mellon University Docket"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2035580"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2097191"},{"key":"e_1_3_2_1_53_1","first-page":"351","volume-title":"Int. Symposium on Design and Test","author":"Wu Y.-R.","year":"2010","unstructured":"Y.-R. Wu , S.-Y. Kao , and S.-A. Hwang ,\"\" Minimizing ECO Routing for FIB\",\"Proc. Int. Symposium on Design and Test , 2010 , pp. 351 -- 354 . Y.-R. Wu, S.-Y. Kao, and S.-A. Hwang,\"\"Minimizing ECO Routing for FIB\",\"Proc. Int. Symposium on Design and Test, 2010, pp. 351--354."}],"event":{"name":"ISPD'11: International Symposium on Physical Design","sponsor":["SIGDA ACM Special Interest Group on Design Automation"],"location":"Santa Barbara CA USA","acronym":"ISPD'11"},"container-title":["Proceedings of the 2011 international symposium on Physical design"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1960397.1960404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1960397.1960404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:48:53Z","timestamp":1750240133000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1960397.1960404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,27]]},"references-count":52,"alternative-id":["10.1145\/1960397.1960404","10.1145\/1960397"],"URL":"https:\/\/doi.org\/10.1145\/1960397.1960404","relation":{},"subject":[],"published":{"date-parts":[[2011,3,27]]},"assertion":[{"value":"2011-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}