Главная
Study mode:
on
1
Intro
2
The Decremental SSSP Problem
3
Total update times in the approximate setting
4
The ES-structure for maintaining SSSP-tree
5
Lazy version of the ES structure
6
Approximation factor, DAG
7
Extending to general graphs
8
One-way separators
9
Our goal
10
Picking a good BFS layer
11
Quality of the approximate topological order
Description:
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

IEEE
Add to list
0:00 / 0:00