Campus Event Calendar
Event Entry
What and Who
Approximate Shortest Paths via Hop Sets: Distributed and Dynamic Algorithms
Sebastian Krinninger
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 9 February 2016
13:00
30 Minutes
Warning: Title has changed!
E1 4
024
Saarbrücken
Abstract
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.
Contact
Sebastian Krinninger
--email hidden
passcode not visible
logged in users only
Sebastian Krinninger, 02/08/2016 23:10
Sebastian Krinninger, 01/21/2016 15:29 -- Created document.
Sebastian Krinninger, 01/21/2016 15:29 -- Created document.