Massively Parallel Algorithms for Approximate Shortest Paths

Michal Dory, Shaked Matar

We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $poly(\log \log n)$ rounds…