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 $n\Delta_\sigma$ in the worst case, where $n$ is the number of nodes of the network. If $\Delta_\sigma = o(n^2)$, 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.
A Fully Dynamic Algorithm for Distributed Shortest Paths
CICERONE, SERAFINO;DI STEFANO, GABRIELE;FRIGIONI, DANIELE;
2003-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 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 $n\Delta_\sigma$ in the worst case, where $n$ is the number of nodes of the network. If $\Delta_\sigma = o(n^2)$, 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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
