Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approximate Shortest Paths via Hop Sets: Distributed and Dynamic Algorithms
Speaker:Sebastian Krinninger
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 9 February 2016
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Sebastian Krinninger
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Sebastian Krinninger, 01/21/2016 03:29 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Sebastian Krinninger, 02/08/2016 11:10 PM
  • Sebastian Krinninger, 01/21/2016 03:29 PM -- Created document.