Near-Optimal Decremental SSSP in Dense Weighted Digraphs

Near-Optimal Decremental SSSP in Dense Weighted Digraphs

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Our goal

9 of 11

9 of 11

Our goal

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

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.