Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing

IEEE via YouTube

Overview

Explore a 23-minute IEEE conference talk on advanced graph algorithms, focusing on deterministic decremental reachability, strongly connected components (SCC), and shortest paths. Delve into the innovative approach using directed expanders and congestion balancing presented by researchers from Rutgers University, University of Copenhagen, and TTIC. Learn about the motivation behind this research, the concept of directed expanders, directed sparse cuts, decomposition techniques, and the lift operation. Gain insights into cutting-edge developments in graph theory and their applications to efficient algorithm design for dynamic graph problems.

Syllabus

Introduction
Strongly Connected Components
Motivation
Deterministic Decremental SCC
Directed Expanders
Directed sparse cuts
Decomposition
Lift

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

Start your review of Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing

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.