Efficient parallel algorithms for computing all pair shortest paths in directed graphs

被引：23

作者：

Han, YJ

Pan, VY

Reif, JH

机构：

[1] UNIV KENTUCKY,DEPT COMP SCI,LEXINGTON,KY 40506

[2] CUNY HERBERT H LEHMAN COLL,DEPT MATH & COMP SCI,BRONX,NY 10468

[3] DUKE UNIV,DEPT COMP SCI,DURHAM,NC 27706

来源：

ALGORITHMICA | 1997年 / 17卷 / 04期

关键词：

analysis of algorithms; design of algorithms; parallel algorithms; graph algorithms; shortest path;

D O I：

10.1007/BF02523680

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：399 / 415

页数：17

共 19 条

[1] ALON N, 1991, 32ND P ANN IEEE S F, P569
[2] DEKEL E, 1983, IEEE T COMPUT, V32, P307, DOI 10.1109/TC.1983.1676223
[3] PARALLEL MATRIX AND GRAPH ALGORITHMS
DEKEL, E
NASSIMI, D
SAHNI, S
[J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (04) : 657 - 675
[4] Dijkstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390
[5] ALGORITHM-97 - SHORTEST PATH
FLOYD, RW
[J]. COMMUNICATIONS OF THE ACM, 1962, 5 (06) : 345 - 345
[6] Fredman M. L., 1976, SIAM Journal on Computing, V5, P83, DOI 10.1137/0205006
[7] AN IMPROVED PARALLEL ALGORITHM THAT COMPUTES THE BFS NUMBERING OF A DIRECTED GRAPH
GAZIT, H
MILLER, GL
[J]. INFORMATION PROCESSING LETTERS, 1988, 28 (02) : 61 - 65
[8] EFFICIENT ALGORITHMS FOR SHORTEST PATHS IN SPARSE NETWORKS
JOHNSON, DB
[J]. JOURNAL OF THE ACM, 1977, 24 (01) : 1 - 13
[9] LINGAS A, 1990, LECT NOTES COMPUT SC, V450, P447
[10] PAIGE RC, 1986, P INT C PAR PROC ST, P14

← 1 2 →