# 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.

**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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 549 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: **http://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},`

`}`