An Optimal Distributed Algorithm for All-Pairs Shortest-Path
| Data(s) |
23/12/2009
23/12/2009
2004
|
|---|---|
| Resumo |
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. |
| Identificador |
1313-0463 |
| Idioma(s) |
en |
| Publicador |
Institute of Information Theories and Applications FOI ITHEA |
| Palavras-Chave | #Distributed Algorithm #All-Pairs Shortest-Path #Computer Network |
| Tipo |
Article |
