✦ LIBER ✦

A fully dynamic algorithm for distributed shortest paths

✍ Scribed by Serafino Cicerone; Gabriele Di Stefano; Daniele Frigioni; Umberto Nanni

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 297 KB
Volume: 297
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00619-9

No coin nor oath required. For personal study only.

✦ Synopsis

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 modiÿcation (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 modiÿcation. 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.

📜 SIMILAR VOLUMES

Fully Dynamic Algorithms for Maintaining

Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

✍ Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal quer

A distributed shortest-paths algorithm w

A distributed shortest-paths algorithm with distance-dependent message complexities

✍ Kouji Miura; Toshimitsu Masuzawa; Nobuki Tokura 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 948 KB

## Abstract This paper presents a distributed algorithm for the single‐source shortest‐paths problem in a network with nonnegative integral link weights. Its message complexity is , where __n__ is the number of processors, __e__ is the number of links, and __D__ is the maximum distance from the ro

Dynamic algorithms for shortest paths in

Dynamic algorithms for shortest paths in planar graphs

✍ Esteban Feuerstein; Alberto Marchetti-Spaccamela 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 887 KB

An ‘All Pairs Shortest Paths’ Distribute

An ‘All Pairs Shortest Paths’ Distributed Algorithm Using 2n2Messages

✍ S. Haldar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 279 KB

In an execution of a distributed program, processes communicate among themselves by exchanging messages. The execution speed of the program could be expedited by a faster message delivery system, transmitting messages to their destinations through their respective shortest paths. Some distributed al

A bicriterion shortest path algorithm

✍ João Carlos Namorado Climaco; Ernesto Queirós Vieira Martins 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 386 KB

A shortest path algorithm for grid graph

A shortest path algorithm for grid graphs

✍ F. O. Hadlock 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 547 KB