Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient parallel algorithms for computing all pair shortest paths in directed graphs (1997).
| Content Provider | CiteSeerX |
|---|---|
| Author | Han, Yijie Pan, V. Y. Reif, J. H. |
| Abstract | . We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O( f (n)/p + I (n) log n) on the PRAM using p processors, where I (n) is log n on the EREW PRAM, log log n on the CCRW PRAM, f (n) is o(n 3 ). On the randomized CRCW PRAM we are able to achieve time complexity O(n 3 /p + log n) using p processors. Key Words. Analysis of algorithms, Design of algorithms, Parallel algorithms, Graph algorithms, Shortest path. 1. Introduction. A number of known algorithms compute the all pair shortest paths in graphs and digraphs with n vertices by using O(n 3 ) operations [D], [Fl], [J]. All these algorithms, however, use at least n-1 recursive steps in the worst case and thus require at least the order of n time in their parallel implementation, even if the number of available processors is not bounded. O(n) time and n 2 processor bounds can indeed be achieved, for instance, in the straightforward parallelization of th... |
| File Format | |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Directed Graph Pair Shortest Path Efficient Parallel Algorithm Time Complexity Known Algorithm Parallel Implementation Processor Bound N-1 Recursive Step Parallel Algorithm Straightforward Parallelization Ccrw Pram Graph Algorithm Shortest Path Available Processor Log Log Present Parallel Algorithm Erew Pram Crcw Pram |
| Content Type | Text |
