Max-Planck-Institut für Informatik
max planck institut
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:Fully dynamic all-pairs shortest paths with worst-case update-time revisited
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
Date, Time and Location
Date:Thursday, 15 December 2016
Duration:30 Minutes
Building:E1 4 - MPI-INF
We revisit the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph. The allowed updates are insertions and deletions of nodes and their incident edges. We give worst-case guarantees on the time needed to process a single update (in contrast to related results, the update time is not amortized over a sequence of updates).

Our main result is a simple randomized algorithm that for any parameter $c>1$ has a worst-case update time of $ O (cn^{2+2/3} \log^{4/3}{n}) $ and answers distance queries correctly with probability $1-1/n^c$, against an adaptive online adversary if the graph contains no negative cycle. The best deterministic algorithm is by Thorup [STOC 2005] with a worst-case update time of $ \tilde O (n^{2+3/4})$ and assumes non-negative weights. This is the first improvement for this problem for more than a decade. Conceptually, our algorithm shows that randomization along with a more direct approach can provide better bounds.

Joint work with Ittai Abraham and Shiri Chechik
To appear in SODA 2017

Name(s):Sebastian Krinninger
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Sebastian Krinninger, 11/30/2016 10:49 PM
Last modified:
Uwe Brahm/MPII/DE, 12/15/2016 07:01 AM
  • Sebastian Krinninger, 12/09/2016 03:13 PM
  • Sebastian Krinninger, 11/30/2016 10:49 PM -- Created document.