In recent years, the Massively Parallel Computation (MPC) model has gained significant attention. However, most distributed and parallel graph algorithms in the MPC model are designed for static graphs. Dynamic graph algorithms can deal with graph changes more efficiently than the corresponding static graph algorithms. Moreover, a few parallel dynamic graph algorithms (such as the graph connectivity) in the MPC model have been proposed and shown superiority over their parallel static counterparts. However, there are no existing dynamic all-pairs shortest paths (APSP) algorithms working in the MPC model.
Improved algorithm in parallel computation model is faster than existing static parallel APSP algorithms
