Dynamic Graph Algorithms: What We Know and What We Don’t | Richard M. Karp Distinguished Lecture

Monika Henzinger surveys algorithms that maintain graph information as vertices and edges change. The lecture explains major algorithmic techniques and open problems, and shows how dynamic data structures support applications such as clustering and recent breakthroughs in static maximum-flow and minimum-cost-flow algorithms.