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

Hilfe Wegweiser Impressum Kontakt Einloggen

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Fully dynamic shortest paths and negative cycle detection on diagraphs with Arbitrary Arc Weights

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

Frigioni,  Daniele
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

1998-1-009
(beliebiger Volltext), 11KB

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

Frigioni, D., Marchetti-Spaccamela, A., & Nanni, U.(1998). Fully dynamic shortest paths and negative cycle detection on diagraphs with Arbitrary Arc Weights (MPI-I-1998-1-009). Saarbrücken: Max-Planck-Institut für Informatik.

Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-7BD9-A
Zusammenfassung
We study the problem of maintaining the distances and the shortest paths from a source node in a directed graph with arbitrary arc weights, when weight updates of arcs are performed. We propose algorithms that work for any digraph and have optimal space requirements and query time. If a negative--length cycle is introduced during weight decrease operations it is detected by the algorithms. The proposed algorithms explicitly deal with zero--length cycles. The cost of update operations depends on the class of the considered digraph and on the number of the output updates. We show that, if the digraph has a $k$-bounded accounting function (as in the case of digraphs with genus, arboricity, degree, treewidth or pagenumber bounded by $k$) the update procedures require $O(k\cdot n\cdot \log n)$ worst case time. In the case of digraphs with $n$ nodes and $m$ arcs $k=O(\sqrt{m})$, and hence we obtain $O(\sqrt{m}\cdot n \cdot \log n)$ worst case time per operation, which is better for a factor of $O(\sqrt{m} / \log n)$ than recomputing everything from scratch after each input update. If we perform also insertions and deletions of arcs all the above bounds become amortized.