Completed
The Decremental SSSP Problem
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
Automatically move to the next video in the Classroom when playback concludes
- 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
