Decremental Shortest Paths Against an Adaptive Adversary

Explore a comprehensive lecture on decremental single-source shortest paths in dynamic graphs undergoing deletions. Delve into Aaron Bernstein's near-optimal deterministic data structure that maintains (1+ε)-approximate distance/path estimates with m^(1+o(1)) total update time. Discover how this breakthrough removes the oblivious adversary assumption from previous results. Examine the novel framework that treats low-diameter graphs like expanders, allowing for the utilization of expander properties without the limitations of expander decomposition. Gain insights into this significant advancement in dynamic graph algorithms and its implications for algorithm design.

Decremental Shortest Paths against an Adaptive Adversary