Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


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

Frigioni, D. and Marchetti-Spaccamela, A. and Nanni, U.

MPI-I-98-1-009. April 1998, 18 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-98-1-009.ps549 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},