Decremental Single Source Shortest Paths in Near-Linear Time

EADS talk by Danupon Nanongkai, KTH Royal Institute of Technology, Sweden.


The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge weighted undirected graph G undergoing edge deletions, where the edge weights are integers from 1 to W. In this talk, I will discuss the recent randomized (1+ε)-approximation algorithm with O(m1+o(1)log W) total update time for this problem. I will also discuss the main technique which is maintaining a so-called sparse (d, ε)-hop set. A (d, ε)-hop set of a graph G=(V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1+ε)-approximated by their d-hop distance (given by a path containing at most d edges) on G'=(V, E ∪ E'). Our algorithm can maintain an (no(1), ε)-hop set of near-linear size in near-linear time.

Danupon Nanongkai is currently an assistant professor at the department of Theoretical Computer Science, KTH Royal Institute of Technology, Sweden. He received a Ph.D. in Algorithms, Combinatorics, and Optimization from Georgia Tech, USA, in 2011. His thesis co-won the Principles of Distributed Computing Doctoral Dissertation Award in 2013. His research interest is generally on graph algorithms and particularly on distributed, dynamic, and approximation graph algorithms.