✦ LIBER ✦
A distributed shortest-paths algorithm with distance-dependent message complexities
✍ Scribed by Kouji Miura; Toshimitsu Masuzawa; Nobuki Tokura
- Publisher
- John Wiley and Sons
- Year
- 1994
- Tongue
- English
- Weight
- 948 KB
- Volume
- 25
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
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 root. The known shortest‐paths algorithm with the distance‐dependent message complexity requires O(min(Dn + e, n^2^)) messages. The algorithm of this paper is more efficient for networks with D = o(n^3^/e) and D = ω__(e/n).__ Moreover, the breadth‐first search tree problem is considered.