Efficient parallel algorithms for computing all pair shortest paths in directed graphs |
| |
| Authors: | Yijie Han V. Y. Pan J. H. Reif |
| |
| Affiliation: | (1) Department of Computer Science, University of Kentucky, 40506 Lexington, KY, USA;(2) Present address: Electronic Data Systems, Inc., 300 E. Big Beaver Road, Mail Stop 408, 48083 Troy, MI, USA;(3) Department of Mathematics and Computer Science, Lehman College, CUNY, 10468 Bronx, NY, USA;(4) Department of Computer Science, Duke University, 27706 Durham, NC, USA |
| |
| Abstract: | We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexityO(f(n)/p+I(n)logn) on the PRAM usingp processors, whereI(n) is logn on the EREW PRAM, log logn on the CCRW PRAM,f(n) iso(n 3). On the randomized CRCW PRAM we are able to achieve time complexityO(n 3/p+logn) usingp processors. A preliminary version of this paper was presented at the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992. Support by NSF Grant CCR 90-20690 and PSC CUNY Awards #661340 and #662478. |
| |
| Keywords: | Analysis of algorithms Design of algorithms Parallel algorithms Graph algorithms Shortest path |
| 本文献已被 SpringerLink 等数据库收录！ |
|
