𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by S. Haldar

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
279 KB
Volume
24
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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 algorithms have been proposed in recent years for determining all pairs shortest paths for an Ž 2 . arbitrary computer network. The best known algorithm uses O n log n messages, where n is the number of computers in the network. This paper presents a new distributed algorithm for the same problem using 2 n 2 messages in the worst case. This algorithm uses a strategy quite different from those of the other algorithms for the same problem.

📜 SIMILAR VOLUMES

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a