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

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs. In an $m$-edge graph undergoing edge inse…