Massively parallel algorithms for fully dynamic all-pairs shortest paths

doi:10.1007/s11704-024-3452-2

Front. Comput. Sci.

2024, Vol. 18

Issue (4) : 184611 https://doi.org/10.1007/s11704-024-3452-2

Information Systems

Massively parallel algorithms for fully dynamic all-pairs shortest paths

Chilei WANG¹, Qiang-Sheng HUA¹(

), Hai JIN¹, Chaodong ZHENG²

¹. National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
². State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China

Download: PDF(314 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Corresponding Author(s): Qiang-Sheng HUA

Just Accepted Date: 10 January 2024 Issue Date: 03 April 2024

Cite this article:

Chilei WANG,Qiang-Sheng HUA,Hai JIN, et al. Massively parallel algorithms for fully dynamic all-pairs shortest paths[J]. Front. Comput. Sci., 2024, 18(4): 184611.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-024-3452-2
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I4/184611

	Rounds	Memory	CC	EW	Query	Type
Karczmarz et al. [8]	$O (d), (d ∈ [1, n])$	$O ~ (n 3)$	$O ~ (n 3)$	Real	Distances	Deterministic
Cao et al. [9]	$O (n 3 / 2 + o (1))$	$O ~ (n 3)$	$O ~ (n 3)$	Integer	Distances/Paths	Randomized
AEV of Hajiaghayi et al. [7]	$O (n / α)$	$O (n 3 ? α / 2)$	$O (n 3 log ? n)$	Real	Distances/Paths	Deterministic
ADP of Abraham et al. [2]	$O ~ (n 2 + 2 / 3)$	$O (n α) ∗$	$O ~ (n 2 + 2 / 3)$	Real	Distances/Paths	Randomized
This work	$O (n 23 ? α 6 l o g n / α)$	$O (n 3 ? α / 2)$	$O (n 3 l o g n)$	Real	Distances/Paths	Randomized

Tab.1 Comparing our parallel fully dynamic APSP algorithm with the existing works

1	Dinitz M, Nazari Y. Massively parallel approximate distance sketches. In: Proceedings of the 23rd International Conference on Principles of Distributed Systems. 2019, 35: 1−35: 17
2	Abraham I, Chechik S, Krinninger S. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In: Proceedings of the 28th Annual ACM SIAM Symposium on Discrete Algorithms. 2017, 440−452
3	X, Zhu W, Li Y, Yang J Wang . Incremental algorithms for the maximum internal spanning tree problem. Science China Information Sciences, 2021, 64( 5): 152103
4	M R, Henzinger V King . Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing, 2001, 31( 2): 364–374
5	G F, Italiano S, Lattanzi V S, Mirrokni N Parotsidis . Dynamic algorithms for the massively parallel computation model. In: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. 2019, 49−58
6	P, Sao R, Kannan P, Gera R W Vuduc . A supernodal all-pairs shortest path algorithm. In: Proceedings of the 25th SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2020, 250−261
7	M, Hajiaghayi S, Lattanzi S, Seddighin C Stein . MapReduce meets fine-grained complexity: MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond. 2019, arXiv preprint arXiv: 1905.01748
8	Karczmarz A, Sankowski P. A deterministic parallel APSP algorithm and its applications. In: Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. 2021, 255−272
9	Cao N, Fineman J T. Parallel exact shortest paths in almost linear work and square root depth. In: Proceedings of 2023 ACM-SIAM Symposium on Discrete Algorithms. 2023, 4354−4372

[1]	FCS-23452-OF-CW_suppl_1	Download
[2]	FCS-23452-OF-CW_suppl_2	Download

Viewed

Full text

Abstract

Cited

Shared

Discussed