Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

PhD Open


Dynamic Graph Algorithms

Prelegent: Christian Wulff-Nilsen

2019-11-14 14:15

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