Massively Parallel Algorithms for Approximate Shortest Paths
Michal Dory, Shaked Matar · 2024
We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take poly(łogłogn ) rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with n vertices and m edges.