Near-Optimal Decremental SSSP in Dense Weighted Digraphs

Explore a 22-minute IEEE conference talk on near-optimal decremental single-source shortest paths (SSSP) in dense weighted digraphs. Delve into the research by Aaron Bernstein, Maximilian P. Gutenberg, and Christian Wulff-Nilsen from Rutgers University and the University of Copenhagen. Learn about the decremental SSSP problem, total update times in approximate settings, and the ES-structure for maintaining SSSP-trees. Discover the lazy version of the ES structure, approximation factors, and directed acyclic graphs (DAGs). Examine the extension to general graphs, one-way separators, and the process of picking a good BFS layer. Gain insights into the quality of approximate topological orders and the researchers' goals in addressing this complex algorithmic challenge.

Intro
The Decremental SSSP Problem
Total update times in the approximate setting
The ES-structure for maintaining SSSP-tree
Lazy version of the ES structure
Approximation factor, DAG
Extending to general graphs
One-way separators
Our goal
Picking a good BFS layer
Quality of the approximate topological order