A DISTRIBUTED SHORTEST-PATHS ALGORITHM WITH DISTANCE-DEPENDENT MESSAGE COMPLEXITIES

Authors
MIURA K MASUZAWA T TOKURA N
Citation
K. Miura et al., A DISTRIBUTED SHORTEST-PATHS ALGORITHM WITH DISTANCE-DEPENDENT MESSAGE COMPLEXITIES, Systems and computers in Japan, 25(9), 1994, pp. 53-66
Citations number
7
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Information Systems","Computer Science Theory & Methods
Journal title
Systems and computers in Japan → ACNP
ISSN journal
08821666
Volume
25
Issue
9
Year of publication
1994
Pages
53 - 66
Database
ISI
SICI code
0882-1666(1994)25:9<53:ADSAWD>2.0.ZU;2-#
Abstract
This paper presents a distributed algorithm for the single-source shor test-paths problem in a network with nonnegative integral link weights . Its message complexity is O(square root nDe + e), where n is the num ber of processors, e is the number of links, and D is the maximum dist ance from the root. The known shortest-paths algorithm with the distan ce-dependent message complexity requires O(min(Dn + e, n2)) messages. The algorithm of this paper is more efficient for networks with D = o( n3/e) and D = omega(e/n). Moreover, the breadth-first search tree prob lem is considered.