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

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 61972447 and 61832006).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

Supporting information

The supporting information is available online at journal.hep.com.cn and link.springer.com.

RIGHTS & PERMISSIONS

2024 Higher Education Press