{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:41:05Z","timestamp":1780674065999,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,3,25]],"date-time":"2018-03-25T00:00:00Z","timestamp":1521936000000},"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":[[2018,3,25]]},"DOI":"10.1145\/3177540.3178239","type":"proceedings-article","created":{"date-parts":[[2018,3,16]],"date-time":"2018-03-16T12:53:36Z","timestamp":1521204816000},"page":"10-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Prim-Dijkstra Revisited"],"prefix":"10.1145","author":[{"given":"Charles J.","family":"Alpert","sequence":"first","affiliation":[{"name":"Cadence Design Systems Inc., Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wing-Kai","family":"Chow","sequence":"additional","affiliation":[{"name":"Cadence Design Systems Inc., Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kwangsoo","family":"Han","sequence":"additional","affiliation":[{"name":"Cadence Design Systems Inc. & University of California, San Diego, Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew B.","family":"Kahng","sequence":"additional","affiliation":[{"name":"University of California, San Diego, San Diego, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhuo","family":"Li","sequence":"additional","affiliation":[{"name":"Cadence Design Systems Inc., Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Derong","family":"Liu","sequence":"additional","affiliation":[{"name":"Cadence Design Systems Inc., Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sriram","family":"Venkatesh","sequence":"additional","affiliation":[{"name":"University of California, San Diego, San Diego, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,3,25]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.391737"},{"key":"e_1_3_2_1_2_1","volume-title":"https:\/\/www.semiconductors.org\/clientuploads\/Research_Technology\/ITRS\/2013\/2013Interconnect.pdf","author":"Edition ITRS","year":"2013","unstructured":"ITRS 2013 Edition Report - Interconnect , https:\/\/www.semiconductors.org\/clientuploads\/Research_Technology\/ITRS\/2013\/2013Interconnect.pdf , 2013 . ITRS 2013 Edition Report - Interconnect, https:\/\/www.semiconductors.org\/clientuploads\/Research_Technology\/ITRS\/2013\/2013Interconnect.pdf, 2013."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758762"},{"key":"e_1_3_2_1_4_1","volume-title":"Nov.","author":"Alpert C. J.","year":"2016","unstructured":"C. J. Alpert , Personal Communication , Nov. 2016 . C. J. Alpert, Personal Communication, Nov. 2016."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.46785"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147012"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.137519"},{"key":"e_1_3_2_1_11_1","first-page":"103","volume-title":"Proc. SODA","author":"Kortsarz G.","year":"1997","unstructured":"G. Kortsarz and D. Peleg ,\" Approximating Shallow-light Trees \", Proc. SODA , 1997 , pp. 103 -- 110 . G. Kortsarz and D. Peleg,\"Approximating Shallow-light Trees\", Proc. SODA, 1997, pp. 103--110."},{"key":"e_1_3_2_1_12_1","first-page":"243","volume-title":"Proc. SODA","author":"Khuller S.","year":"1993","unstructured":"S. Khuller , B. Raghavachari and N. Young ,\" Balancing Minimum Spanning Trees and Shortest-path Trees \", Proc. SODA , 1993 , pp. 243 -- 250 . S. Khuller, B. Raghavachari and N. Young,\"Balancing Minimum Spanning Trees and Shortest-path Trees\", Proc. SODA, 1993, pp. 243--250."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/645460.654092"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/157485.164656"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.144853"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.331412"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704371353"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/157485.165065"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2363-2","volume-title":"On Optimal Interconnections for VLSI","author":"Kahng A. B.","year":"1995","unstructured":"A. B. Kahng and G. Robins , On Optimal Interconnections for VLSI , Kluwer Academic Publishers , 1995 . A. B. Kahng and G. Robins, On Optimal Interconnections for VLSI, Kluwer Academic Publishers,1995."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_3_2_1_21_1","unstructured":"L. Scheffer Bookshelf RMST code http:\/\/vlsicad.ucsd.edu\/GSRC\/bookshelf\/Slots\/RSMT\/RMST\/.  L. Scheffer Bookshelf RMST code http:\/\/vlsicad.ucsd.edu\/GSRC\/bookshelf\/Slots\/RSMT\/RMST\/."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90045-5"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90124-0"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.329264"},{"key":"e_1_3_2_1_25_1","volume-title":"US Patent","author":"He L.","year":"2013","unstructured":"L. He , S. Yao , W. Deng , J. Chen and L. Chao ,\" Interconnect Routing Methods of Integrated Circuit Designs \", US Patent 8386984, Feb. 2013 . L. He, S. Yao, W. Deng, J. Chen and L. Chao,\"Interconnect Routing Methods of Integrated Circuit Designs\", US Patent 8386984, Feb. 2013."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","DOI":"10.1515\/9783899498264","volume-title":"US Patent","author":"Bose S.","year":"2012","unstructured":"S. Bose ,\"Methods and Systems for Placement and Routing\" , US Patent 8332793, Dec. 2012 . S. Bose,\"Methods and Systems for Placement and Routing\", US Patent 8332793, Dec. 2012."},{"key":"e_1_3_2_1_27_1","volume-title":"US Patent","author":"Hentschke R. F.","year":"2012","unstructured":"R. F. Hentschke , M. de Oliveira Johann , J. Narasimhan and R. A. de Luz Reis ,\"Methods and Apparatus for Providing Flexible Timing-driven Routing Trees\" , US Patent 8095904, Jan. 2012 . R. F. Hentschke, M. de Oliveira Johann, J. Narasimhan and R. A. de Luz Reis,\"Methods and Apparatus for Providing Flexible Timing-driven Routing Trees\", US Patent 8095904, Jan. 2012."},{"key":"e_1_3_2_1_28_1","volume-title":"US Patent","author":"Furnish G. M.","year":"2011","unstructured":"G. M. Furnish , M. J. LeBrun and S. Bose , \" Tunneling as a Boundary Congestion Relief Mechanism \", US Patent 7921393, Apr. 2011 . G. M. Furnish, M. J. LeBrun and S. Bose, \"Tunneling as a Boundary Congestion Relief Mechanism\", US Patent 7921393, Apr. 2011."},{"key":"e_1_3_2_1_29_1","volume-title":"US Patent","author":"Furnish G. M.","year":"2011","unstructured":"G. M. Furnish , M. J. LeBrun and S. Bose ,\" Node Spreading Via Artificial Density Enhancement to Reduce Routing Congestion \", US Patent 7921392, Apr. 2011 . G. M. Furnish, M. J. LeBrun and S. Bose,\"Node Spreading Via Artificial Density Enhancement to Reduce Routing Congestion\", US Patent 7921392, Apr. 2011."},{"key":"e_1_3_2_1_30_1","volume-title":"US Patent","author":"Saxena P.","year":"2010","unstructured":"P. Saxena , V. Khandelwal , C. Qiao , P-H. Ho , J. C. Lin and M. A. Iyer ,\" Interconnect-driven Physical Synthesis using Persistent Virtual Routing \", US Patent 7853915, Dec. 2010 . P. Saxena, V. Khandelwal, C. Qiao, P-H. Ho, J. C. Lin and M. A. Iyer,\"Interconnect-driven Physical Synthesis using Persistent Virtual Routing\", US Patent 7853915, Dec. 2010."},{"key":"e_1_3_2_1_31_1","volume-title":"US Patent","author":"Alpert C. J.","year":"2006","unstructured":"C. J. Alpert , J. Hu and P. H. Villarrubia ,\" Practical Methodology for Early Buffer and Wire Resource Allocation \", US Patent 6996512, Feb. 2006 . C. J. Alpert, J. Hu and P. H. Villarrubia,\"Practical Methodology for Early Buffer and Wire Resource Allocation\", US Patent 6996512, Feb. 2006."},{"key":"e_1_3_2_1_32_1","volume-title":"US Patent","author":"Alpert C. J.","year":"2003","unstructured":"C. J. Alpert , R. G. Gandham , J. Hu , S. T. Quay and A. J. Sullivan ,\" Apparatus and Method for Determining Buffered Steiner Trees for Complex Circuits \", US Patent 6591411, Jul. 2003 . C. J. Alpert, R. G. Gandham, J. Hu, S. T. Quay and A. J. Sullivan,\"Apparatus and Method for Determining Buffered Steiner Trees for Complex Circuits\", US Patent 6591411, Jul. 2003."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/13094791X"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0149-4"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2017.8203828"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228500"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2391263"}],"event":{"name":"ISPD '18: International Symposium on Physical Design","location":"Monterey California USA","acronym":"ISPD '18","sponsor":["SIGDA ACM Special Interest Group on Design Automation"]},"container-title":["Proceedings of the 2018 International Symposium on Physical Design"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177540.3178239","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3177540.3178239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:50Z","timestamp":1750273550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177540.3178239"}},"subtitle":["Achieving Superior Timing-driven Routing Trees"],"short-title":[],"issued":{"date-parts":[[2018,3,25]]},"references-count":38,"alternative-id":["10.1145\/3177540.3178239","10.1145\/3177540"],"URL":"https:\/\/doi.org\/10.1145\/3177540.3178239","relation":{},"subject":[],"published":{"date-parts":[[2018,3,25]]},"assertion":[{"value":"2018-03-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}