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 vertices 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 vertices of the network. If $\Delta_{\sigma} = o(n^2)$, this is better than recomputing everything from scratch after each edge modification. Up to now it was only known that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths
A Fully Dynamic Algorithm for Distributed Shortest Paths
CICERONE, SERAFINO;DI STEFANO, GABRIELE;FRIGIONI, DANIELE;
2000-01-01
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 vertices 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 vertices of the network. If $\Delta_{\sigma} = o(n^2)$, this is better than recomputing everything from scratch after each edge modification. Up to now it was only known that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest pathsPubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
