{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T03:05:24Z","timestamp":1769655924715,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","funder":[{"name":"National Natural Science Foundation of China","award":["62272122"],"award-info":[{"award-number":["62272122"]}]},{"name":"Guangzhou Municipality Big Data Intelligence Key Lab","award":["2023A03J0012"],"award-info":[{"award-number":["2023A03J0012"]}]},{"name":"Hong Kong CRF grants","award":["C7004-22G"],"award-info":[{"award-number":["C7004-22G"]}]},{"name":"Hong Kong CRF grants","award":["C6015-23G"],"award-info":[{"award-number":["C6015-23G"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,1,28]]},"DOI":"10.1145\/3774934.3786461","type":"proceedings-article","created":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T15:25:57Z","timestamp":1769613957000},"page":"204-217","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["ROME: Maximizing GPU Efficiency for All-Pairs Shortest Path via Taming Fine-Grained Irregularities"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2875-0056","authenticated-orcid":false,"given":"Weile","family":"Luo","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0791-5361","authenticated-orcid":false,"given":"Yuhan","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2478-1512","authenticated-orcid":false,"given":"Xiangrui","family":"Yu","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2986-967X","authenticated-orcid":false,"given":"Qiang","family":"Wang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-7492-2069","authenticated-orcid":false,"given":"Ruibo","family":"Fan","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6961-6394","authenticated-orcid":false,"given":"Hongyuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, Hoboken, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9745-4372","authenticated-orcid":false,"given":"Xiaowen","family":"Chu","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"},{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2026,1,28]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"2023. Supernodal-Floyd-Warshall: An Implementation of the Supernodal Floyd-Warshall Algorithm. https:\/\/github.com\/programelot\/Supernodal-Floyd-Warshall"},{"key":"e_1_3_2_1_2_1","unstructured":"2025. cuGraph \u2013 RAPIDS Graph Analytics Library. https:\/\/github.com\/rapidsai\/cugraph Accessed: 2025\u201108\u201115"},{"key":"e_1_3_2_1_3_1","unstructured":"2025. CUTLASS: Fast Linear Algebra in CUDA C++. https:\/\/github.com\/NVIDIA\/cutlass"},{"key":"e_1_3_2_1_4_1","volume-title":"On a routing problem. Quarterly of applied mathematics, 16, 1","author":"Bellman Richard","year":"1958","unstructured":"Richard Bellman. 1958. On a routing problem. Quarterly of applied mathematics, 16, 1 (1958), 87\u201390."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178492"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018756"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370321"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/iiswc.2012.6402918"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/tpds.2015.2485994"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3545008.3545056"},{"key":"e_1_3_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2033","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. isbn:0262033844","edition":"3"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.45"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Edsger W Dijkstra et al. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1 1 (1959) 269\u2013271.","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.008"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.46"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_3_2_1_17_1","unstructured":"Lester R Ford Jr. 1956. Network flow theory. Rand Corp Santa Monica Ca."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"GregN. Frederickson. 1987. Fast Algorithms for Shortest Paths in Planar Graphs with Applications. SIAM Journal on Computing SIAM Journal on Computing Dec.","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_1_19_1","volume-title":"Tarjan","author":"Fredman Michael L.","year":"1984","unstructured":"Michael L. Fredman and Robert E. Tarjan. 1984. Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms. J. ACM."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","unstructured":"Alan George. 1973. Nested Dissection of a Regular Finite Element Mesh. SIAM J. Numer. Anal. Apr 345\u2013363. https:\/\/doi.org\/10.1137\/0710032 10.1137\/0710032","DOI":"10.1137\/0710032"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.598277"},{"key":"e_1_3_2_1_22_1","volume-title":"International conference on high-performance computing. 197\u2013208","author":"Harish Pawan","year":"2007","unstructured":"Pawan Harish and Petter J Narayanan. 2007. Accelerating large graph algorithms on the GPU using CUDA. In International conference on high-performance computing. 197\u2013208."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433708"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3571885.3571892"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1413957.1413966"},{"key":"e_1_3_2_1_27_1","unstructured":"RichardJ. Lipton and RobertE. Tarjan. 1977. A separator theorem for planar graphs. Oct."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Weile Luo. 2025. Artifact for the paper: ROME: Maximizing GPU Efficiency for All-Pairs Shortest Path via Taming Fine-Grained Irregularities. https:\/\/doi.org\/10.5281\/zenodo.17709850 10.5281\/zenodo.17709850","DOI":"10.5281\/zenodo.17709850"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295716"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145832"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3173162.3173180"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984015"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Fran\u00e7ois Pellegrini. 2012. Scotch and PT-scotch graph partitioning software: an overview. Combinatorial Scientific Computing 373\u2013406.","DOI":"10.1201\/b11644-15"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374533"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ipdps.2018.00100"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1996.548468"},{"key":"e_1_3_2_1_42_1","first-page":"2","article-title":"A blocked all-pairs shortest-paths algorithm","volume":"8","author":"Venkataraman Gayathri","year":"2003","unstructured":"Gayathri Venkataraman, Sartaj Sahni, and Srabani Mukhopadhyaya. 2003. A blocked all-pairs shortest-paths algorithm. Journal of Experimental Algorithmics (JEA), 8 (2003), 2\u20132.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441605"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Oren Weimann and Raphael Yuster. 2009. Computing the Girth of a Planar Graph in O(n logn) Time. 764\u2013773. https:\/\/doi.org\/10.1007\/978-3-642-02927-1_63 10.1007\/978-3-642-02927-1_63","DOI":"10.1007\/978-3-642-02927-1_63"},{"key":"e_1_3_2_1_47_1","volume-title":"2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 190\u2013200","author":"Xia Yang","year":"2022","unstructured":"Yang Xia, Peng Jiang, Gagan Agrawal, and Rajiv Ramnath. 2022. Scaling and selecting GPU methods for all pairs shortest paths (APSP) computations. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 190\u2013200."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3577193.3593728"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018754"}],"event":{"name":"PPoPP '26: 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming","location":"Sydney NSW Australia","acronym":"PPoPP '26","sponsor":["SIGHPC ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing","SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774934.3786461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T15:29:42Z","timestamp":1769614182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774934.3786461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,28]]},"references-count":49,"alternative-id":["10.1145\/3774934.3786461","10.1145\/3774934"],"URL":"https:\/\/doi.org\/10.1145\/3774934.3786461","relation":{},"subject":[],"published":{"date-parts":[[2026,1,28]]},"assertion":[{"value":"2026-01-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}