Dynamic Graph Algorithms

Speaker(s)

Christian Wulff-Nilsen

Affiliation

University of Copenhagen (DIKU)

Date

Nov. 14, 2019, 2:15 p.m.

Room

room 5440

Seminar

PhD Open

---

Computing shortest paths is a classical algorithmic problem dating back to the 1950s and the algorithms of Dijkstra and Bellman-Ford are typically part of an introductory course on algorithms. One down-side of such algorithms is that they assume the graph to be static. However, real-life networks often change over time and an algorithm like Dijkstra would need to be rerun from scratch even if the graph modelling the network changes by only a small amount, say by a single edge insertion or deletion. In recent years, there has been a lot of active research on dynamic graph algorithms which are tailor-made to efficiently compute a new solution after a small change to the graph. This course will focus on selected results within this exciting area of research. I will focus on dynamic connectivity and on dynamic shortest paths, the latter in both the approximate and exact setting.

 

More info at http://phdopen.mimuw.edu.pl/index.php?page=z19w2

---