MPI-I-98-1-009
Fully dynamic shortest paths and negative cycle detection on diagraphs with Arbitrary Arc Weights
Frigioni, D. and Marchetti-Spaccamela, A. and Nanni, U.
April 1998, 18 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-98-1-009.ps (549 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-009
BibTeX
@TECHREPORT{FrigioniMarchetti-SpaccamelaNanni98,
AUTHOR = {Frigioni, D. and Marchetti-Spaccamela, A. and Nanni, U.},
TITLE = {Fully dynamic shortest paths and negative cycle detection on diagraphs with Arbitrary Arc Weights},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-98-1-009},
MONTH = {April},
YEAR = {1998},
ISSN = {0946-011X},
}