About
Understanding the time complexity of dynamic graph algorithms is a flourishing field of research. Over the last decade there have been significant advances with the development of conditional lower bounds and new algorithmic techniques including dynamic primal-dual-based approximation algorithms, dynamic expander decompositions, and various other dynamic hierarchical graph decompositions. This progress, combined with algorithmic techniques from linear or convex optimization, has enabled recent breakthroughs in static graph algorithms such as maximum flow, bipartite matching, minimum cost flow, etc. However, in these settings, existing dynamic graph algorithms can usually not be applied as a black-box, but instead they have to be adapted to the specific requirements of the static algorithm, leading often to new challenging questions for dynamic graph algorithms researchers. Thus, one goal of this workshop is to bring together researchers working on dynamic graph algorithms and on static graph algorithms to enrich both fields.
Ultimately the goal of the design of any data structure is to give a practical solution to a real-world problem. Indeed, dynamic graphs frequently arise in real-world applications such as in the analysis of social networks or routing in street networks. This immediately leads to the question how well the theoretically best dynamic graph algorithms perform in practice in comparison to ad-hoc dynamic algorithms or even recomputation from scratch. Thus a second goal of the workshop is to bring together the communities working on dynamic algorithms from the practical and the theoretical side.
Chairs/Organizers
