Massively parallel algorithms for fully dynamic all-pairs shortest paths

References

[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] Zhu X, Li W, Yang Y, Wang J . Incremental algorithms for the maximum internal spanning tree problem. Science China Information Sciences, 2021, 64( 5): 152103

[4] Henzinger M R, King V . Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing, 2001, 31( 2): 364–374

[5] Italiano G F, Lattanzi S, Mirrokni V S, Parotsidis N. 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] Sao P, Kannan R, Gera P, Vuduc R W. 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] Hajiaghayi M, Lattanzi S, Seddighin S, Stein C. 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

RIGHTS & PERMISSIONS

Higher Education Press