Deterministic decremental single source shortest paths: beyond the o(mn) bound
Aaron Bernstein, Shiri Chechik · 2016
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions.