# Dynamic Graph Algorithms

Aleksander Bjørn Grodt Christiansen: Algorithms for Dynamic Problems

Data plays an ever-greater role today: whether we are navigating to new destinations or scheduling jobs for people, planes and processors, data plays an important role in arriving at a good solution. As infrastructure increases, road networks and airports expand and, consequently, the data sets become enormous. Massive data sets demand computation schemes or algorithms that are computationally efficient; ideally, they only consider each data point a few times on average. This ensures that the computational resources required scale nicely with the size of the problem being solved. In the classical algorithmic setting, one optimizes with this goal in mind: Given a data set, how efficiently can we calculate the required analysis?

Many modern problems, however, are inherently dynamic: when traffic forms on the highway, it may be faster to reroute your trip, or when a flight is delayed, it might be sensible to restructure the departure schedule for that day. Many of these changes are local; they affect only one data point: the status of a specific highway or airplane. Despite the changes being small, in the classical setting one must reconsider the entire data set to accommodate them. For massive data set this might not be desirable. As such, much recent research has gone into studying dynamic algorithms that can facilitate local updates and recompute good solutions efficiently.

Many modern problems can be modelled as graphs. A graph is a collection of points together with a set of edges or connections between the points. Typically, the edges model compatibility or conflict. For instance, a road network can be modeled by viewing locations as points and connections between them as edges. A route can then be viewed as a consecutive sequence of edges in the corresponding graph. Many problems share the same underlying abstract structure; matching resources to processors is no different from matching planes to trips. Thus, if one can solve the abstracted version of the problem, one develops tools that can be applied in many different settings and arenas. 2 The goal of this project is to use tools from mathematics and computer science to devise and analyze algorithms that efficiently recompute solutions to such abstract problems on dynamic graphs.

## PhD project

By: Aleksander Bjørn Grodt Christiansen

Section: AlgoLoG

Principal supervisor: Eva Rotenberg

Co-supervisors: Inge Li Gørtz, Carsten Thomassen

Project title: Dynamic Graph Algorithms

Term: 15/10/2021 → 14/10/2024

## Contact

Aleksander Bjørn Grodt Christiansen
PhD student
DTU Compute

## Contact

Eva Rotenberg
Associate Professor
DTU Compute
+45 45 25 50 05

Inge Li Gørtz
Professor
DTU Compute
+45 45 25 36 73

## Contact

Carsten Thomassen
Professor
DTU Compute
+45 45 25 30 58
https://www.compute.dtu.dk/english/phd/current-phd/phd-algolog/aleksander-bjoern-grodt-christiansen
7 DECEMBER 2023