Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/858

 Title: An Optimal Distributed Algorithm for All-Pairs Shortest-Path Authors: Kanchi, SarojaVineyard, David Keywords: Distributed AlgorithmAll-Pairs Shortest-PathComputer Network Issue Date: 2004 Publisher: Institute of Information Theories and Applications FOI ITHEA Abstract: In this paper the network problem of determining all-pairs shortest-path is examined. A distributed algorithm which runs in O(n) time on a network of n nodes is presented. The number of messages of the algorithm is O(e+n log n) where e is the number of communication links of the network. We prove that this algorithm is time optimal. URI: http://hdl.handle.net/10525/858 ISSN: 1313-0463 Appears in Collections: Volume 11 Number 2

Files in This Item:

File Description SizeFormat