MADALGO Theory Seminar

MADALGO Seminar: Sebastian Krinninger (Max-Planck-Institut für Informatik): "Approximate Shortest Paths via Hop Sets: Distributed and Dynamic Algorithms"

2016.08.03 | Katrine Østerlund Rasmussen

Date Thu 18 Aug
Time 14:15 15:00
Location Nygaard 295

Approximate Shortest Paths via Hop Sets: Distributed and Dynamic Algorithms

In this talk, I discuss a technique for computing approximate single-source shortest paths using a hop set. A hop set is a set of weighted edges that, when added to the graph, allows to approximate all distances by using only a few edges. This approach was previously used by Cohen in the PRAM model [STOC '94]. I will show how to obtain almost tight approximate SSSP algorithms in both the distributed setting (CONGEST model) and the centralized deletions-only setting using a suitable hop set. 

Joint work with Monika Henzinger and Danupon Nanongkai.    

Host: Thomas Dueholm