Dynamic Graph Algorithms
Christian Wulff-Nilsen, University of Copenhagen (DIKU).
Course Summary |
About the lecturer |
Location and schedule |
Materials |
Assignment
Course summary:
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.
About the lecturer:
Christian Wulff-Nilsen is associate professor in computer science at the University of Copenhagen where he has been a member of the faculty since 2012. His Bachelor's, Master's and PhD degrees were obtained at University of Copenhagen as well. After his PhD, he spent two years as postdoc, the first year at Carleton University and the second year at University of Southern Denmark, before returning to University of Copenhagen.
Christian's current main area of research is within algorithms and data structures for dynamic graphs. He has a four-year Sapere Aude Starting Grant from the Independent Research Fund Denmark. The focus of this grant is on algorithms for shortest paths and other graph problems, both in dynamic and the static setting. In addition, he is part of the Basic Algorithms Research Copenhagen (BARC) center at University of Copenhagen. He has three Phd students, two from his Sapere Aude grant and one from BARC.
MIMUW, room 5440.
|
|
|
||||||||||||||||||||||||||