{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T07:50:35Z","timestamp":1765871435728,"version":"3.48.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T00:00:00Z","timestamp":1756771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T00:00:00Z","timestamp":1756771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972447"],"award-info":[{"award-number":["61972447"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61832006"],"award-info":[{"award-number":["61832006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["CCF Trans. HPC"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s42514-025-00234-1","type":"journal-article","created":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T14:54:24Z","timestamp":1756824864000},"page":"479-493","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A parallel all-pairs shortest paths algorithm for dynamic graphs"],"prefix":"10.1007","volume":"7","author":[{"given":"Lin","family":"Zhu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3909-5719","authenticated-orcid":false,"given":"Qiang-sheng","family":"Hua","sequence":"additional","affiliation":[]},{"given":"Hai","family":"Jin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,2]]},"reference":[{"key":"234_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492914000038","volume":"23","author":"G Ballard","year":"2014","unstructured":"Ballard, G., Carson, E.C., Demmel, J., Hoemmen, M., Knight, N., Schwartz, O.: Communication lower bounds and optimal algorithms for numerical linear algebra. Acta Numer. 23, 1\u2013155 (2014)","journal-title":"Acta Numer."},{"key":"234_CR2","doi-asserted-by":"crossref","unstructured":"Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Graph expansion and communication costs of fast matrix multiplication. In Proc. the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, 4\u20136 June, pp. 1\u201312, ACM, (2011)","DOI":"10.1145\/1989493.1989495"},{"key":"234_CR3","doi-asserted-by":"crossref","unstructured":"Ballard, G., Demmel, J., Holtz, O., Lipshitz, B., Schwartz, O.: Communication-optimal parallel algorithm for Strassen's matrix multiplication. In Proc. the 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Pittsburgh, PA, USA, 25\u201327 June, pp.193\u2013204, ACM, (2012)(","DOI":"10.1145\/2312005.2312044"},{"key":"234_CR4","doi-asserted-by":"crossref","unstructured":"Ballard, G., Bulu\u00e7, A., Demmel, J., Grigori, L., Lipshitz, B., Schwartz, O., Toledo, S.: Communication optimal parallel multiplication of sparse random matrices. In Proc. the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Montreal, QC, Canada, 23\u201325 July, pp.222\u2013231\u00e7, ACM, (2013)","DOI":"10.1145\/2486159.2486196"},{"key":"234_CR5","doi-asserted-by":"crossref","unstructured":"Ballard, G., Demmel, J., Grigori, L., Jacquelin, M., Knight, N.: A 3d parallel algorithm for QR decomposition. In Proc. the 30rd on Symposium on Parallelism in Algorithms and Architecture}, Vienna, Austria, 16\u201318 July, pp.55\u201365, ACM, (2018)","DOI":"10.1145\/3210377.3210415"},{"issue":"1\u20133","key":"234_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0304-3975(02)00619-9","volume":"297","author":"S Cicerone","year":"2003","unstructured":"Cicerone, S., Stefano, G.D., Frigioni, D., Nanni, U.: A fully dynamic algorithm for distributed shortest paths. Theor. Comput. Sci. 297(1\u20133), 83\u2013102 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"7\u20139","key":"234_CR7","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1016\/j.tcs.2009.11.008","volume":"411","author":"S Cicerone","year":"2010","unstructured":"Cicerone, S., D\u2019Angelo, G., Stefano, G.D., Frigioni, D.: Partially dynamic efficient algorithms for distributed shortest paths. Theor. Comput. Sci. 411(7\u20139), 1013\u20131037 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"234_CR8","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G. F.: A new approach to dynamic all pairs shortest paths. In Proc. the 35th Annual ACM Symposium on Theory of Computing, San Diego, CA, {USA}, 9\u201311 June, pp.159\u2013166, ACM, (2003)","DOI":"10.1145\/780542.780567"},{"key":"234_CR9","doi-asserted-by":"crossref","unstructured":"Demmel, J., Eliahu, D., Fox, A., Kamil, S., Lipshitz, B., Schwartz, O., Spillinger, O.: Communication-optimal parallel recursive rectangular matrix multiplication. In Proc. the 27th IEEE International Symposium on Parallel and Distributed Processing, Cambridge, MA, USA 20\u201324 May, pp.261\u2013272, IEEE Computer Society, (2013)","DOI":"10.1109\/IPDPS.2013.80"},{"key":"234_CR10","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Durfee, D., Kulkarni, J., Peng, R., Sawlani, S., Sun, X.: Parallel batch-dynamicgraphs: Algorithms and lower bounds. In Proc. the 2020 ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, USA, 5\u20138 January, pp.1300\u20131319, SIAM, (2020)","DOI":"10.1137\/1.9781611975994.79"},{"issue":"1","key":"234_CR11","first-page":"1","volume":"28","author":"S Even","year":"1981","unstructured":"Even, S., Shiloach, Y.: An on-line edge-deletion problem J. . ACM 28(1), 1\u20134 (1981)","journal-title":". ACM"},{"issue":"6","key":"234_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: Shortest path. Commun. ACM 5(6), 345 (1962)","journal-title":"Commun. ACM"},{"issue":"2","key":"234_CR13","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"A George","year":"1973","unstructured":"George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10(2), 345\u2013363 (1973)","journal-title":"SIAM J. Numer. Anal."},{"issue":"3","key":"234_CR14","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1109\/TKDE.2017.2772233","volume":"30","author":"S Greco","year":"2018","unstructured":"Greco, S., Molinaro, C., Pulice, C.: Efficient maintenance of shortest distances in dynamic graphs. IEEE Trans. Knowl. Data Eng. 30(3), 474\u2013487 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"234_CR15","doi-asserted-by":"crossref","unstructured":"Greco, S., Molinaro, C., Pulice, C.: Efficient maintenance of all-pairs shortest distances. In Proc. the 28th International Conference on Scientific and Statistical Database Managemen, Budapest, Hungary, 18\u201320 July, pp.9:1\u20139:12, ACM, (2016)","DOI":"10.1145\/2949689.2949713"},{"key":"234_CR16","doi-asserted-by":"crossref","unstructured":"Gutenberg, M. P., Wulff-Nilsen, C.: Fully-dynamic all-pairs shortest paths: Improved worst-case time and space bounds. In Proc. the 2020 ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, USA, 5\u20138 January, pp. 2562\u20132574, SIAM, (2020)","DOI":"10.1137\/1.9781611975994.156"},{"key":"234_CR17","doi-asserted-by":"crossref","unstructured":"Hong, J., Kung, H. T.: I\/O complexity: The red-blue pebble game. In Proc. The 13rd Annual ACM Symposium on Theory of Computing, Milwaukee, Wisconsin, USA, 11\u201313 May, pp.326\u2013333, ACM, (1981)","DOI":"10.1145\/800076.802486"},{"issue":"11","key":"234_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-020-2931-x","volume":"64","author":"Q Hua","year":"2021","unstructured":"Hua, Q., Qian, L., Yu, D., Shi, X., Jin, H.: A nearly optimal distributed algorithm for computing the weighted girth. Sci. China Inf. Sci 64(11), 1\u201315 (2021)","journal-title":"Sci. China Inf. Sci"},{"key":"234_CR19","doi-asserted-by":"crossref","unstructured":"Hutter, E., Solomonik, E.: Communication avoiding cholesky-qr2 for rectangular matrices. In Proc. the 2019 IEEE International Parallel and Distributed Processing Symposium, Hilton Copacabana, Rio de Janeiro, Brazil, 20\u201324 May, pp.89\u2013100, IEEE, (2019)","DOI":"10.1109\/IPDPS.2019.00020"},{"issue":"9","key":"234_CR20","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/j.jpdc.2004.03.021","volume":"64","author":"D Irony","year":"2004","unstructured":"Irony, D., Toledo, S., Tiskin, A.: Communication lower bounds for distributed-memory matrix multiplication. J. Parallel Distributed Comput 64(9), 1017\u20131026 (2004)","journal-title":"J. Parallel Distributed Comput"},{"key":"234_CR21","doi-asserted-by":"crossref","unstructured":"Italiano, G. F., Lattanzi, S., Mirrokni, V. S., Parotsidis, N.: Dynamic algorithms for the massively parallel computation model. In Proc. The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, Phoenix, AZ, USA, 22\u201324 June, pp.49\u201358, ACM, (2019)","DOI":"10.1145\/3323165.3323202"},{"key":"234_CR22","unstructured":"Jenq, J., Sahni, S.: All pairs shortest paths on a hypercube multiprocessor. In Proc. International Conference on Parallel Processing, Park, PA, USA, 18\u201321 August, pp.713\u2013716, Pennsylvania State University Press, (1987)"},{"issue":"5","key":"234_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-020-2996-2","volume":"65","author":"L Jia","year":"2022","unstructured":"Jia, L., Hua, Q., Fan, H., Wang, Q., Jin, H.: Efficient distributed algorithms for holistic aggregation functions on random regular graphs. Sci. China Inf. Sci 65(5), 1\u201319 (2022)","journal-title":"Sci. China Inf. Sci"},{"issue":"1","key":"234_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1\u201313 (1977)","journal-title":"J. ACM"},{"issue":"1","key":"234_CR25","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"234_CR26","doi-asserted-by":"crossref","unstructured":"Khopkar, S. S., Nagi, R., Nikolaev, A. G.: An efficient map-reduce algorithm for the incremental computation of all-pairs shortest paths in social networks. In Proc. the 2012 International Conference on Advances in Social Networks Analysis and Mining, Istanbul, Turkey, 26\u201329 August, pp.1144\u20131148, IEEE Computer Society, (2012)","DOI":"10.1109\/ASONAM.2012.197"},{"key":"234_CR27","doi-asserted-by":"crossref","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proc. the 40th Annual Symposium on Foundations of Computer Science, New York, NY, USA, 17\u201318 October, pp.81\u201391, IEEE Computer Society, (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"234_CR28","doi-asserted-by":"crossref","unstructured":"Nowicki, K., Onak, K.: Dynamic graph algorithms with batch updates in the massively parallel computation model. In Proc. the 2021 ACM-SIAM Symposium on Discrete Algorithms, Virtual Conference, 10\u201313 January, pp.2939\u20132958, SIAM, (2021)","DOI":"10.1137\/1.9781611976465.175"},{"issue":"9","key":"234_CR29","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1109\/TPDS.2004.44","volume":"15","author":"J Park","year":"2004","unstructured":"Park, J., Penner, M., Prasanna, V.K.: Optimizing graph algorithms for improved cache performance. IEEE Trans. Parallel Distributed Syst 15(9), 769\u2013782 (2004)","journal-title":"IEEE Trans. Parallel Distributed Syst"},{"key":"234_CR30","doi-asserted-by":"crossref","unstructured":"Solomonik, E., Bulu\u00e7, A., Demmel, J.: Minimizing communication in all-pairs shortest paths. In Proc. the 27th IEEE International Symposium on Parallel and Distributed Processing, Cambridge, MA, USA, 20\u201324 May, pp.548\u2013559, IEEE Computer Society, (2013)","DOI":"10.1109\/IPDPS.2013.111"},{"issue":"1","key":"234_CR31","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1177\/1094342005051521","volume":"19","author":"R Thakur","year":"2005","unstructured":"Thakur, R., Rabenseifner, R., Gropp, W.: Optimization of collective communication operations in MPICH. Int. J. High Perform. Comput. Appl. 19(1), 49\u201366 (2005)","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"234_CR32","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In Proc. the 37th Annual ACM Symposium on Theory of Computing}, Baltimore, MD, USA, 22\u201324 May, pp. 112\u2013119, ACM, (2005)","DOI":"10.1145\/1060590.1060607"},{"key":"234_CR33","doi-asserted-by":"crossref","unstructured":"Tiskin, A.: All-pairs shortest paths computation in the BSP model. In Proc. Automata, Languages and Programming, 28th International Colloquium, Crete, Greece, 8\u201312 July, pp.178\u2013189, Springer, (2001)","DOI":"10.1007\/3-540-48224-5_15"},{"key":"234_CR34","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on boolean matrices. J. ACM 9, 11\u201312 (1962)","journal-title":"J. ACM"},{"key":"234_CR35","doi-asserted-by":"crossref","unstructured":"Yang, C., Miller, B. P.: Critical path analysis for the execution of parallel and distributed programs. In Proc. the 8th International Conference on Distributed Computing Systems, San Jose, California, USA, 13\u201317 June, pp.366\u2013373, IEEE Computer Society, (1988)","DOI":"10.1109\/DCS.1988.12538"}],"container-title":["CCF Transactions on High Performance Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42514-025-00234-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42514-025-00234-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42514-025-00234-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T07:47:20Z","timestamp":1765871240000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42514-025-00234-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,2]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["234"],"URL":"https:\/\/doi.org\/10.1007\/s42514-025-00234-1","relation":{},"ISSN":["2524-4922","2524-4930"],"issn-type":[{"type":"print","value":"2524-4922"},{"type":"electronic","value":"2524-4930"}],"subject":[],"published":{"date-parts":[[2025,9,2]]},"assertion":[{"value":"15 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}