de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

#### Fully Dynamic All-pairs Shortest Paths with Worst-case Update-time revisited

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons199379

Krinninger,  Sebastian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

1607.05132.pdf
(Preprint), 609KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Abraham, I., Chechik, S., & Krinninger, S. (2016). Fully Dynamic All-pairs Shortest Paths with Worst-case Update-time revisited. Retrieved from http://arxiv.org/abs/1607.05132.

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.