Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

We study dynamic $(1+\epsilon )$-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected $n$-node $m$-edge graphs under edge deletions. The fastest algor…