ALCOMFT-TR-01-32

Serafino Cicerone, Gabriele Di Stefano, Daniele Frigioni and Umberto Nanni
A Fully Dynamic Algorithm for Distributed Shortest Paths
Rome. Work packages 2 and 4. March 2001.

Abstract: We propose a fully-dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If \Delta_\sigma is the number of pairs of nodes changing the distance after a single edge modification \sigma (insert, delete, weight-decrease, or weight-increase) then the message complexity of the proposed algorithm is O(n \Delta_\sigma) in the worst case, where n is the number of nodes of the network. If \Delta_\sigma = o(n²), this is better than recomputing everything from scratch after each edge modification. Up to now only a result of Ramarao and Venkatesan was known, stating that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths.

Postscript file: ALCOMFT-TR-01-32.ps.gz (137 kb).