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

Please use this identifier to cite or link to this item:

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.
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!   Creative Commons License DSpace Software Copyright © 2002-2009  The DSpace Foundation - Feedback