IMI-BAS
 

BulDML at Institute of Mathematics and Informatics >
ITHEA >
International Journal ITA >
2004 >
Volume 11 Number 2 >

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, Saroja
Vineyard, David
Keywords: Distributed Algorithm
All-Pairs Shortest-Path
Computer 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
ijita11-2-p06.pdf73.34 kBAdobe PDFView/Open

 



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2009  The DSpace Foundation - Feedback