How fast can you update your MST? (Dynamic algorithms for cluster computing)

Seth Gilbert, Lawrence Li

Imagine a large graph that is being processed by a cluster of computers, e.g., described by the $k$-machine model or the Massively Parallel Computation Model. The graph, however, i…