{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:17Z","timestamp":1750307717953,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0701821"],"award-info":[{"award-number":["CCF-0701821"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2009,5]]},"abstract":"<jats:p>\n            Previous works on PCB bus routing assume matched pin ordering on both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this article, we propose a preprocessing step to untangle such twisted nets. We also introduce a practical routing style, which we call\n            <jats:italic>single-detour routing<\/jats:italic>\n            , to simplify the untangling problem. We then present a necessary and sufficient condition for the existence of single-detour routing solutions. Furthermore, we present a dynamic-programming-based algorithm to solve the single-detour untangling problem with consideration of wire capacity between adjacent pins. Our algorithm produces an optimal single-detour routing solution that rematches the pin ordering. By integrating our algorithm into the bus router in a previous length-matching router, we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.\n          <\/jats:p>","DOI":"10.1145\/1529255.1529268","type":"journal-article","created":{"date-parts":[[2009,6,2]],"date-time":"2009-06-02T14:51:08Z","timestamp":1243954268000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Theories and algorithms on single-detour routing for untangling twisted bus"],"prefix":"10.1145","volume":"14","author":[{"given":"Tan","family":"Yan","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin D. F.","family":"Wong","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,6,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. The MIT Press.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. The MIT Press."},{"volume-title":"Proceedings of the International Conference on Computer-Aided Design, 390--395","author":"Kong H.","key":"e_1_2_1_2_1","unstructured":"Kong , H. , Yan , T. , Wong , M. D. F. , and Ozdal , M. M . 2007. Optimal bus sequencing for escape routing in dense PCBs . In Proceedings of the International Conference on Computer-Aided Design, 390--395 . Kong, H., Yan, T., Wong, M. D. F., and Ozdal, M. M. 2007. Optimal bus sequencing for escape routing in dense PCBs. In Proceedings of the International Conference on Computer-Aided Design, 390--395."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2004.07.008"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.853685"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.857376"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.882584"},{"key":"e_1_2_1_7_1","article-title":"Busses: What are they and how do they work&quest; Printed Circ","author":"Ritchey L. W.","year":"2000","unstructured":"Ritchey , L. W. 2000 . Busses: What are they and how do they work&quest; Printed Circ . Des. Mag. Ritchey, L. W. 2000. Busses: What are they and how do they work&quest; Printed Circ. Des. Mag.","journal-title":"Des. Mag."},{"key":"e_1_2_1_8_1","unstructured":"Ritchey L. W. and Zasio J. 2003. Right the First Time A Practical Handbook on High Speed PCB and System Design. Speeding Edge.  Ritchey L. W. and Zasio J. 2003. Right the First Time A Practical Handbook on High Speed PCB and System Design. Speeding Edge."},{"key":"e_1_2_1_9_1","volume-title":"The Algorithm Design Manual","author":"Skiena S. S.","unstructured":"Skiena , S. S. 1998. The Algorithm Design Manual , 1 st ed. Springer . Skiena, S. S. 1998. The Algorithm Design Manual, 1st ed. Springer.","edition":"1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Tummala R. R. Rymaszewski E. J. and Klopfenstein A. G. 1997. Microelectronics Packaging Handbook Part II: Semiconductor Packaging. Kluwer Academic.  Tummala R. R. Rymaszewski E. J. and Klopfenstein A. G. 1997. Microelectronics Packaging Handbook Part II: Semiconductor Packaging. Kluwer Academic.","DOI":"10.1007\/978-1-4615-6037-1"},{"key":"e_1_2_1_11_1","unstructured":"Wiens D. 2000. Printed circuit board routing at the threshold. White paper. Mentor Graphics.  Wiens D. 2000. Printed circuit board routing at the threshold. White paper. Mentor Graphics."},{"volume-title":"Proceedings of the International Conference on Computer-Aided Design, 396--400","author":"Yan T.","key":"e_1_2_1_12_1","unstructured":"Yan , T. and Wong , M. D. F. 2007. Untangling twisted nets for bus routing . In Proceedings of the International Conference on Computer-Aided Design, 396--400 . Yan, T. and Wong, M. D. F. 2007. Untangling twisted nets for bus routing. In Proceedings of the International Conference on Computer-Aided Design, 396--400."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1529255.1529268","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1529255.1529268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:26Z","timestamp":1750253426000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1529255.1529268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["10.1145\/1529255.1529268"],"URL":"https:\/\/doi.org\/10.1145\/1529255.1529268","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2009,5]]},"assertion":[{"value":"2008-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}