Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights
Lists
Only you see this
Abstract
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 graph and require linear space and optimal query time. If a negative-length cycle is added during weight-decrease operations it is detected by the algorithms. The algorithms explicitly deal with zero-length cycles. We show that, if the graph has a k-bounded accounting function (as in the case of graphs with genus, arboricity, degree, treewidth or pagenumber bounded by k, and k-inductive graphs) the algorithms require O(k • n • log n) worst case time. In the case of graphs with n nodes and m arcs k = O \( \left( {\sqrt m } \right) \); this gives O(\( \left( {\sqrt m } \right) \) • n • log n) worst case time per operation, which is better for a factor of O(\( \left( {\sqrt m } \right) \)log n) than recomputing everything from scratch after each update.
BibTeX
@inproceedings{frigioni1998fully,
author = {Daniele Frigioni and Alberto Marchetti-Spaccamela and Umberto Nanni},
title = {{Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights}},
booktitle = {ESA},
year = {1998},
doi = {10.1007/3-540-68530-8\_27},
}Loading related content...