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(nDelta(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. (C) 2002 Elsevier Science B.V. All rights reserved.
A fully dynamic algorithm for distributed shortest paths / Serafino, Cicerone; Gabriele Di, Stefano; Daniele, Frigioni; Nanni, Umberto. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 297:1-3(2003), pp. 83-102. (Intervento presentato al convegno 4th Latin American Theoretical Informatics International Conference (LATIN 2000) tenutosi a PUNTA ESTE, URUGUAY nel APR 10-14, 2000) [10.1016/s0304-3975(02)00619-9].
A fully dynamic algorithm for distributed shortest paths
NANNI, Umberto
2003
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(nDelta(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. (C) 2002 Elsevier Science B.V. All rights reserved.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2003_11573-70304.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
296.94 kB
Formato
Adobe PDF
|
296.94 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
