b'@techreport{FrigioniMarchetti-SpaccamelaNanni98,'b'\nTITLE = {Fully dynamic shortest paths and negative cycle detection on diagraphs with Arbitrary Arc Weights},\nAUTHOR = {Frigioni, Daniele and Marchetti-Spaccamela, A. and Nanni, U.},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-1998-1-009},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1998},\nDATE = {1998},\nABSTRACT = {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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'