A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in graphs undergoing edge insertions and/or deletions. In particular, we obtain the following results: