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.
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
Overview
Syllabus
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
Taught by
IEEE FOCS: Foundations of Computer Science
