Decremental Shortest Paths and Beyond
Docentlecture by Danupon Na Nongkai, Theoretical Computer Science (TCS) Department
Tid: Ti 2017-05-16 kl 13.00
Plats: Room 4423, Lindstedtsvägen 5
Medverkande: Danupon Na Nongkai
This lecture focuses on a fundamental problem in dealing with graphs that evolve over time called decremental single-source shortest paths.
This problem concerns maintaining the distances and shortest paths between a given source node and every other node in a graph undergoing edge deletions.
In this talk, I will discuss the recent development on this problem which leads to a randomized (1+ε)-approximation algorithm with near-linear total update time on undirected graphs. I will also discuss the main technique called hop-set which has found many new applications beyond the decremental shortest paths problem.
The talk will also touch some lower bound developments and other variations of the problem.