Decremental APSP in Directed Graphs Versus an Adaptive Adversary

Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg +1

Given a directed graph $G=(V,E)$, undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n=|V|$, we consider the problem of maintaini…