A decentralized algorithm for finding the shortest paths in defense communications networks
By: by Jin Y. Yen
Contributors: Naval Postgraduate School (U.S.)
Publisher: Naval Postgraduate School
Published: 1979
Place of publication: Monterey, Calif
Language: eng
Number of pages: 13
Subjects: Network analysis (Planning); Algorithms
Description: This paper presents a decentralized shortest path algorithm which finds the shortest distances between all pairs of nodes without requiring that any particular node have information about the complete topology of the network. The algorithm requires at most N3/2 additions, N3/2 comparisons, and N3/2 transmissions of simple message between individual nodes. The computational upper bound of the present algorithm is lower than that of Dijkstra's centralized shortest path algorithm and is 1/N of the upper bound of Abram and Rhodes' decentralized shortest path algorithm. (Author)
Notes: Title from cover.

"July 1979"--Cover.

"NPS-55-79-015"--Cover.

Includes bibliographical references (p. 10).

"Approved for public release; distribution unlimited"--Cover.

Technical report; 1979.