A fully dynamic algorithm for distributed shortest paths

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 t...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2003-03, Vol.297 (1), p.83-102
Main Authors: Cicerone, Serafino, Di Stefano, Gabriele, Frigioni, Daniele, Nanni, Umberto
Format: Article
Language:English
Subjects:
Algebra
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
General algebraic systems
Graph theory
Mathematical programming
Mathematics
Operational research and scientific management
Operational research. Management science
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(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.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(02)00619-9