Dynamic Graph Algorithms: What We Know and What We Don’t

A dynamic graph algorithm is a data structure that maintains information about a graph while it is modified through local operations such as edge or vertex insertions or deletions. These data structures can be used in real-world applications such as maintaining clusters in large social networks or as subroutines in static graph algorithms.

The research on designing efficient dynamic graph algorithms started in the 1980s, and in past years has become a popular research field as dynamic graph algorithms are a critical component in recent breakthrough results in static graph algorithms, for example, in the almost-linear time algorithms for maximum flow and minimum-cost flow. In her Richard M. Karp Distinguished Lecture, Monika Henzinger (Institute of Science and Technology Austria) surveyed the state of the art in dynamic graph algorithms, the different algorithmic techniques developed for them, and all the questions in the field that still await an answer.