1165 København K
Ph.d.-forsvar — On 10 December Maximilian Probst Gutenberg will defend his Ph.D. thesis titled "Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs".
Date & Time:
Virtually via Zoom: https://ucph-ku.zoom.us/s/61556899731
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs.
In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions:
These problems have recently received an extraordinary amount of attention due to their role as subproblems in various more complex and notoriously hard graph problems, especially to compute flows, bipartite matchings and cuts. Our techniques lead to the first near-optimal data structures for these problems in various different settings.
In particular, we obtain
Chairperson: Associate professor, Jakob Nordström, Department of Computer Science, UCPH
Professor, Valerie King, University of Victoria
Professor, Uri Zwick, University of Tel Aviv
Associate professor, Christian Wulff-Nilsen, Department of Computer Science, University of Copenhagen
Professor, Mikkel Thorup, Department of Computer Science, University of Copenhagen
Moderator at this defence will be:
Professor, Jon Sporring, Department of Computer Science, University of Copenhagen
For an electronic copy of the thesis, please contact email@example.com