Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time

Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source $s$ to every vertex $v$ in an $m$-edge graph undergoing edge deletion…