{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:48:57Z","timestamp":1774687737436,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"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":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>We present the core elements of BonnRoute: advanced data structures and algorithms for fast and high-quality routing in modern technologies. Global routing is based on a combinatorial approximation scheme for min-max resource sharing. Detailed routing uses exact shortest path algorithms, based on a shape-based data structure for pin access and a two-level track-based data structure for long-distance connections. All algorithms are very fast. Compared to an industrial router (on 32 nm and 22 nm chips), BonnRoute is over two times faster, has 5 % less netlength, 20 % less vias, and reduces detours by more than 90 %.<\/jats:p>","DOI":"10.1145\/2442087.2442103","type":"journal-article","created":{"date-parts":[[2013,4,9]],"date-time":"2013-04-09T12:17:58Z","timestamp":1365509878000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["BonnRoute"],"prefix":"10.1145","volume":"18","author":[{"given":"Michael","family":"Gester","sequence":"first","affiliation":[{"name":"University of Bonn, Bonn"}]},{"given":"Dirk","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn"}]},{"given":"Tim","family":"Nieberg","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn"}]},{"given":"Christian","family":"Panten","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn"}]},{"given":"Christian","family":"Schulte","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn"}]}],"member":"320","published-online":{"date-parts":[[2013,4,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.920691"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735028"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774581"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.486666"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.920686"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Conference on Computer-Aided Design. 338--343","author":"Chang Y.-J.","unstructured":"Chang , Y.-J. , Lee , Y.-T. , and Wang , T . -C. 2008. NTHU-route 2.0: a fast and stable global router . In Proceedings of the International Conference on Computer-Aided Design. 338--343 . Chang, Y.-J., Lee, Y.-T., and Wang, T.-C. 2008. NTHU-route 2.0: a fast and stable global router. In Proceedings of the International Conference on Computer-Aided Design. 338--343."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the IEEE\/ACM Design Automation Conference. 13--19","author":"Chen H.","unstructured":"Chen , H. , Cheng , C.-K. , Kahng , A. , Mandoiu , I. , Wang , Q. , and Yao , B . 2003. The Y-architecture for on-chip interconnect: Analysis and methodology . In Proceedings of the IEEE\/ACM Design Automation Conference. 13--19 . Chen, H., Cheng, C.-K., Kahng, A., Mandoiu, I., Wang, Q., and Yao, B. 2003. The Y-architecture for on-chip interconnect: Analysis and methodology. In Proceedings of the IEEE\/ACM Design Automation Conference. 13--19."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference. 582--587","author":"Chen H.-Y.","unstructured":"Chen , H.-Y. , Hsu , C.-H. , and Chang , Y . -W. 2009. High-performance global routing with fast overflow reduction . In Proceedings of the Asia and South Pacific Design Automation Conference. 582--587 . Chen, H.-Y., Hsu, C.-H., and Chang, Y.-W. 2009. High-performance global routing with fast overflow reduction. In Proceedings of the Asia and South Pacific Design Automation Conference. 582--587."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.884492"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497561.1497575"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 163--167","author":"Cong J.","unstructured":"Cong , J. , Fang , J. , and Khoo , K . 1999. An implicit connection graph maze routing algorithm for ECO routing . In Proceedings of the IEEE International Conference on Computer-Aided Design. 163--167 . Cong, J., Fang, J., and Khoo, K. 1999. An implicit connection graph maze routing algorithm for ECO routing. In Proceedings of the IEEE International Conference on Computer-Aided Design. 163--167."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 396--403","author":"Cong J.","unstructured":"Cong , J. , Fang , J. , and Zhang , Y . 2001. Multilevel approach to full-chip gridless routing . In Proceedings of the IEEE International Conference on Computer-Aided Design. 396--403 . Cong, J., Fang, J., and Zhang, Y. 2001. Multilevel approach to full-chip gridless routing. In Proceedings of the IEEE International Conference on Computer-Aided Design. 396--403."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1231996.1232034"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_16_1","volume-title":"Contour: A tile-based gridless router. WRL Res. Rep. 95\/3, Western Research Laboratory","author":"Dion J.","year":"1995","unstructured":"Dion , J. and Monier , L . 1995 . Contour: A tile-based gridless router. WRL Res. Rep. 95\/3, Western Research Laboratory , Palo Alto, CA . Dion, J. and Monier, L. 1995. Contour: A tile-based gridless router. WRL Res. Rep. 95\/3, Western Research Laboratory, Palo Alto, CA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446232"},{"key":"e_1_2_1_18_1","volume-title":"Voronoi-Diagramme von Achtecken in der Maximum-Metrik. Diploma Thesis","author":"Gester M.","unstructured":"Gester , M. 2009. Voronoi-Diagramme von Achtecken in der Maximum-Metrik. Diploma Thesis , University of Bonn. Gester, M. 2009. Voronoi-Diagramme von Achtecken in der Maximum-Metrik. Diploma Thesis, University of Bonn."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 156--165","author":"Goldberg A.","unstructured":"Goldberg , A. and Harrelson , C . 2005. Computing the shortest path: A<sup>&ast;<\/sup> search meets graph theory . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 156--165 . Goldberg, A. and Harrelson, C. 2005. Computing the shortest path: A<sup>&ast;<\/sup> search meets graph theory. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 156--165."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0804004"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2871543.2871546"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070404"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/368058.368167"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065734"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.5009200"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9260(01)00020-7"},{"key":"e_1_2_1_29_1","volume-title":"Schneller Algorithmus f\u00fcr k\u00fcrzeste Wege in irregul\u00e4ren Gittergraphen. Diploma Thesis","author":"Humpola J.","unstructured":"Humpola , J. 2009. Schneller Algorithmus f\u00fcr k\u00fcrzeste Wege in irregul\u00e4ren Gittergraphen. Diploma Thesis , University of Bonn. Humpola, J. 2009. Schneller Algorithmus f\u00fcr k\u00fcrzeste Wege in irregul\u00e4ren Gittergraphen. Diploma Thesis, University of Bonn."},{"key":"e_1_2_1_30_1","unstructured":"ICCAD. 2009 global routing benchmarks. http:\/\/www.eecs.umich.edu\/~mmoffitt\/iccad2009.html.  ICCAD. 2009 global routing benchmarks. http:\/\/www.eecs.umich.edu\/~mmoffitt\/iccad2009.html."},{"key":"e_1_2_1_31_1","volume-title":"global routing contest and benchmark suite","author":"ISPD.","year":"2007","unstructured":"ISPD. global routing contest and benchmark suite ( 2007 ). http:\/\/www.sigda.org\/ispd2007\/contest.html. ISPD. global routing contest and benchmark suite (2007). http:\/\/www.sigda.org\/ispd2007\/contest.html."},{"key":"e_1_2_1_32_1","volume-title":"global routing contest and benchmark suite","author":"ISPD.","year":"2008","unstructured":"ISPD. global routing contest and benchmark suite ( 2008 ). http:\/\/www.sigda.org\/ispd2008\/contests\/ispd08rc.html. ISPD. global routing contest and benchmark suite (2008). http:\/\/www.sigda.org\/ispd2008\/contests\/ispd08rc.html."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Jansen K. and Zhang H. 2008. Approximation algorithms for general packing problems and their application to the multicast congestion problem. Math. Prog. A 183--206.  Jansen K. and Zhang H. 2008. Approximation algorithms for general packing problems and their application to the multicast congestion problem. Math. Prog. A 183--206.","DOI":"10.1007\/s10107-007-0106-8"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 13th Symposium on Integrated Circuits and Systems Design. 144--149","author":"Johann M.","unstructured":"Johann , M. and Reis , R . 2000. Net by net routing with a new path search algorithm . In Proceedings of the 13th Symposium on Integrated Circuits and Systems Design. 144--149 . Johann, M. and Reis, R. 2000. Net by net routing with a new path search algorithm. In Proceedings of the 13th Symposium on Integrated Circuits and Systems Design. 144--149."},{"key":"e_1_2_1_35_1","unstructured":"Korte B. Pr\u00f6mel H. and Steger A. 1990. Steiner trees in VLSI-layout. In Paths Flows and VLSI-Layout B. Korte L. Lov\u00e1sz H. Pr\u00f6mel and A. Schrijver Eds. Springern.  Korte B. Pr\u00f6mel H. and Steger A. 1990. Steiner trees in VLSI-layout. In Paths Flows and VLSI-Layout B. Korte L. Lov\u00e1sz H. Pr\u00f6mel and A. Schrijver Eds. Springern."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.889373"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1961.5219222"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)80467-7"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1960397.1960411"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.927733"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1929943.1929951"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Massberg J. and Nieberg T. 2012. Rectilinear paths with minimum segment lengths. Discrete Appl. Math. to appear.  Massberg J. and Nieberg T. 2012. Rectilinear paths with minimum segment lengths. Discrete Appl. Math. to appear.","DOI":"10.1016\/j.dam.2011.12.003"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 1st Canadian Conference on Computational Geometry.","author":"Mitchell J.","year":"1989","unstructured":"Mitchell , J. 1989 . An optimal algorithm for shortest rectilinear paths among obstacles . In Proceedings of the 1st Canadian Conference on Computational Geometry. Mitchell, J. 1989. An optimal algorithm for shortest rectilinear paths among obstacles. In Proceedings of the 1st Canadian Conference on Computational Geometry."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2006082"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353629.1353662"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687549"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference. 545--550","author":"Moffitt M. D.","unstructured":"Moffitt , M. D. and Sze , C. N . 2011. Wire synthesizable global routing for timing closure . In Proceedings of the Asia and South Pacific Design Automation Conference. 545--550 . Moffitt, M. D. and Sze, C. N. 2011. Wire synthesizable global routing for timing closure. In Proceedings of the Asia and South Pacific Design Automation Conference. 545--550."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233598"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-011-0023-y"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024724.2024763"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2013991"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000626"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.08.003"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Preparata F. P. and Shamos M. I. 1985. Computational Geometry. Springer.   Preparata F. P. and Shamos M. I. 1985. Computational Geometry. Springer.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923255"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.224054"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77620"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1711932.1711941"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/505348.505355"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1983.1270048"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-25960-2_24"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228499"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2066030"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. 1--6.","author":"Wu T.-H.","unstructured":"Wu , T.-H. , Davoodi , A. , and Linderoth , J . 2011b. Power-driven global routing for multi-supply voltage domains . In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. 1--6. Wu, T.-H., Davoodi, A., and Linderoth, J. 2011b. Power-driven global routing for multi-supply voltage domains. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. 1--6."},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference. 576--581","author":"Xu Y.","unstructured":"Xu , Y. , Zhang , Y. , and Chu , C . 2009. Fastroute 4.0: global router with efficient via minimization . In Proceedings of the Asia and South Pacific Design Automation Conference. 576--581 . Xu, Y., Zhang, Y., and Chu, C. 2009. Fastroute 4.0: global router with efficient via minimization. In Proceedings of the Asia and South Pacific Design Automation Conference. 576--581."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875556"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442087.2442103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2442087.2442103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:19:06Z","timestamp":1750234746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442087.2442103"}},"subtitle":["Algorithms and data structures for fast and good VLSI routing"],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2442087.2442103"],"URL":"https:\/\/doi.org\/10.1145\/2442087.2442103","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}