{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:42Z","timestamp":1750308762441,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T00:00:00Z","timestamp":1187308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0093273\/0401682"],"award-info":[{"award-number":["CCR-0093273\/0401682"]}],"id":[{"id":"10.13039\/100000001","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":[[2007,8,17]]},"abstract":"<jats:p>This article develops circuit-simulated routing algorithms. We model the routing graph by an RC network with terminals as inputs, and show that the faster an output reaches its peak, the higher the possibility for the corresponding Hanan or escape node to become a Steiner point. This enables us to select Steiner points and then apply any minimum spanning tree algorithm to obtain obstacle-free or obstacle-aware Steiner routing. Compared with existing algorithms, our algorithms have significant gain on either wirelength or runtime for obstacle-free routing, and on both wirelength and runtime for obstacle-aware routing.<\/jats:p>","DOI":"10.1145\/1255456.1255465","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Circuit-simulated obstacle-aware Steiner routing"],"prefix":"10.1145","volume":"12","author":[{"given":"Yiyu","family":"Shi","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA"}]},{"given":"Paul","family":"Mesa","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA"}]},{"given":"Hao","family":"Yu","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA"}]},{"given":"Lei","family":"He","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA"}]}],"member":"320","published-online":{"date-parts":[[2008,5,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1109\/PGEC.1967.264620"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/332357.332368"},{"doi-asserted-by":"crossref","unstructured":"Atkinson D. and van Steenwijk F. J. 1999. Infinite resistive lattices. Am. J. Phys. 486--492.  Atkinson D. and van Steenwijk F. J. 1999. Infinite resistive lattices. Am. J. Phys. 486--492.","key":"e_1_2_1_3_1","DOI":"10.1119\/1.19311"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/1055137.1055145"},{"volume-title":"Proceedings of the ISCAS.","author":"Ganley J. L.","unstructured":"Ganley , J. L. and Cohoon , J. P . 1994. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles . In Proceedings of the ISCAS. Ganley, J. L. and Cohoon, J. P. 1994. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. In Proceedings of the ISCAS.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","article-title":"The rectilinear Steiner tree problem is NP-complele. SIAM","author":"Garey M. R.","year":"1977","unstructured":"Garey , M. R. and Johnson , D. S. 1977 . The rectilinear Steiner tree problem is NP-complele. SIAM J. Appl. Math., 826--834. Garey, M. R. and Johnson, D. S. 1977. The rectilinear Steiner tree problem is NP-complele. SIAM J. Appl. Math., 826--834.","journal-title":"J. Appl. Math., 826--834."},{"doi-asserted-by":"crossref","unstructured":"Hadlock. 1977. A shortest path algorithm for grid graphs. Networks 323--334.  Hadlock. 1977. A shortest path algorithm for grid graphs. Networks 323--334.","key":"e_1_2_1_7_1","DOI":"10.1002\/net.3230070404"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/800260.809014"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1120725.1120732"},{"unstructured":"Hwang F. K. Richards D. S. and Winter P. 1992. The Steiner tree problem. of Annals of Discrete Mathematcis vol. 53 North-Holland Amsterdam The Netherlands.  Hwang F. K. Richards D. S. and Winter P. 1992. The Steiner tree problem. of Annals of Discrete Mathematcis vol. 53 North-Holland Amsterdam The Netherlands.","key":"e_1_2_1_10_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1119772.1119955"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1109\/43.144853"},{"doi-asserted-by":"crossref","unstructured":"Kahng A. B. and Robins G. 1995. On Optimal Interconnections for VLSI. Kluwer Academic Boston MA.  Kahng A. B. and Robins G. 1995. On Optimal Interconnections for VLSI. Kluwer Academic Boston MA.","key":"e_1_2_1_13_1","DOI":"10.1007\/978-1-4757-2363-2"},{"unstructured":"Magma. 2007. The Magma Website. http:\/\/www:magma--da:com\/c\/@ei_ci_2hsu:41ji\/pages\/productsintro:html.  Magma. 2007. The Magma Website. http:\/\/www:magma--da:com\/c\/@ei_ci_2hsu:41ji\/pages\/productsintro:html.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","article-title":"A new heuristic for rectilinear Steiner trees","author":"Mandoiuand I. I.","year":"2000","unstructured":"Mandoiuand , I. I. , Vazirani , V. V. , and Ganley , J. L. 2000 . A new heuristic for rectilinear Steiner trees . IEEE Trans. Comput. Aided Des. Mandoiuand, I. I., Vazirani, V. V., and Ganley, J. L. 2000. A new heuristic for rectilinear Steiner trees. IEEE Trans. Comput. Aided Des.","journal-title":"IEEE Trans. Comput. Aided Des."},{"volume-title":"Proceedings of the IFIPS.","author":"Mikami K.","unstructured":"Mikami , K. and Tabuchi , K . 1968. A computer program for optimal routing printed circuit connectors . In Proceedings of the IFIPS. Mikami, K. and Tabuchi, K. 1968. A computer program for optimal routing printed circuit connectors. In Proceedings of the IFIPS.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1109\/43.712097"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/775832.775860"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1109\/T-C.1974.224054"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/1146909.1147011"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/800095.803072"},{"unstructured":"Warme D. W. et al. Geosteiner 3.1. package.  Warme D. W. et al. Geosteiner 3.1. package.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"crossref","unstructured":"Zachariasen M. and Winter P. 1999. Obstacle-Avoiding Euclidean Steiner trees in the plane: An exact algorithm. In extended abstract presented at the Workshop on Algorithm Engineering and Experimentation.   Zachariasen M. and Winter P. 1999. Obstacle-Avoiding Euclidean Steiner trees in the plane: An exact algorithm. In extended abstract presented at the Workshop on Algorithm Engineering and Experimentation.","key":"e_1_2_1_23_1","DOI":"10.1007\/3-540-48518-X_17"},{"doi-asserted-by":"crossref","unstructured":"Zelikovsky A. 1993. An 11\/6-approximation for the network Steiner tree problem. Algorithmica 463--470.  Zelikovsky A. 1993. An 11\/6-approximation for the network Steiner tree problem. Algorithmica 463--470.","key":"e_1_2_1_24_1","DOI":"10.1007\/BF01187035"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1109\/43.486276"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/640000.640034"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255456.1255465","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1255456.1255465","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:28Z","timestamp":1750278148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255456.1255465"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,17]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8,17]]}},"alternative-id":["10.1145\/1255456.1255465"],"URL":"https:\/\/doi.org\/10.1145\/1255456.1255465","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2007,8,17]]},"assertion":[{"value":"2006-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}