Dynamic graph algorithms and complexity (a survey)

In this talk I will attempt to answer the following questions I have been asked quite often: What are the current challenges in dynamic graph algorithms? What are good starting points for people who want to try working in this field? The talk will focus on challenges for basic graph problems (e.g. connectivity, shortest paths, maximum matching), and will survey some existing upper and lower bound results and techniques.


11am, room G50, 3rd floor, building G (viale Regina Elena 295/B).

Danupon Nanongkai is currently an associate professor in the Theoretical Computer Science group at KTH Royal Institute of Technology, Sweden. He received a Ph.D. in Algorithms, Combinatorics, and Optimization (ACO) from Georgia Tech in 2011 and a docent (aka habilitation) in Computer Science from KTH in 2017. He was awarded the Principles of Distributed Computing Doctoral Dissertation Award in 2013 and an ERC Starting Grant in 2016. His research interest is generally on graph algorithms and complexity, where the current focus is on distributed and dynamic graph algorithms.

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma