We propose a fully-dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If δσ is the number of pairs of nodes changing the distance after a single edge modification σ (insert, delete, weight-decrease, or weight-increase) then the message complexity of the proposed algorithm is O(nδσ) in the worst case, where n is the number of nodes of the network. If δσ = o(n2), this is better than recomputing everything from scratch after each edge modification.
A fully dynamic algorithm for distributed shortest paths / Cicerone, Serafino; Di Stefano, Gabriele; Frigioni, Daniele; Nanni, Umberto. - 1776:(2000), pp. 247-257. (Intervento presentato al convegno 4th Latin American Symposium on Theoretical Informatics, LATIN 2000 tenutosi a Punta del Este; Uruguay) [10.1007/10719839_25].
A fully dynamic algorithm for distributed shortest paths
Frigioni, Daniele;Nanni, Umberto
2000
Abstract
We propose a fully-dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If δσ is the number of pairs of nodes changing the distance after a single edge modification σ (insert, delete, weight-decrease, or weight-increase) then the message complexity of the proposed algorithm is O(nδσ) in the worst case, where n is the number of nodes of the network. If δσ = o(n2), this is better than recomputing everything from scratch after each edge modification.| File | Dimensione | Formato | |
|---|---|---|---|
|
Cicerone_A-Fully-Dynamic_2000.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
147.78 kB
Formato
Adobe PDF
|
147.78 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
