English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

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

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.

Item is

Files

show Files
hide Files
:
MPI-I-98-1-009.pdf (Any fulltext), 13MB
Name:
MPI-I-98-1-009.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Frigioni, Daniele1, Author              
Marchetti-Spaccamela, A.2, Author
Nanni, U.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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 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.

Details

show
hide
Language(s): eng - English
 Dates: 1998
 Publication Status: Published in print
 Pages: 18 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-1998-1-009
BibTex Citekey: FrigioniMarchetti-SpaccamelaNanni98
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -