Improved *Deterministic* Algorithms for Partially Dynamic Shortest Paths.

15/03/2018 - 12:00

Computing shortest paths is one of the fundamental problems of graph algorithms.

The goal of *dynamic* single source shortest paths (SSSP) is to maintain a shortest path tree from a fixed source s as the edges of the graph change over time. 
The most general case is the fully dynamic one, where each adversarial update inserts or deletes an arbitrary edge. The trivial algorithm is to recompute SSSP after every update in O(m) time. For the fully dynamic case, no non-trivial algorithm is known.

We can, however, improve upon the trivial algorithm by restricting the update sequence to be partially dynamic: only insertions (referred to as incremental), or only deletions (referred to as decremental).