Dynamic Graph Algorithms and Their Implementation

Explore dynamic graph algorithms and their implementation in this 56-minute conference talk by Monika Henzinger from the University of Vienna. Gain insights into recent advances in the field, covering both theoretical analysis and empirical evaluations. Delve into topics such as undirected graphs, conditional lower bounds, hierarchical graph decomposition, spanning trees, and local algorithms. Learn about the challenges, advantages, and future directions of dynamic graph algorithms, including their applications in various fields. Engage with audience questions and discover the potential for crossfertilization between different areas of research in this comprehensive presentation organized by the Society for Industrial and Applied Mathematics.

Syllabus

Introduction
Operations
Performance
Motivations
Undirected graphs
Conditional lower bound
Hierarchical graph decomposition
Spanning trees
Segment type
Local algorithms
Random algorithms
Advantages
Other Advantages
Challenges
Data
Batches
Conferences
Summary
Favorite Future Work
Additional Properties
Audience Questions
Crossfertilization