Parallel Algorithms for a Class of Graph Theoretic Problems

概要

論文の詳細を見る
Different from the known algorithms to compute the all pair shortest paths for a weighted, directed grgph G=(V, E, C0ST), an O(|V|^3/p) parallel algorithm running on the CREW PRAMs with p, 1≤p≤|V|^2, processors is presented, which not only computes the distance from vertex i to vertex j in G, but also records the forward and backward shortest path trees rooted at i, i∈V, of G. For any pair i, j∈V, the shortest path P from i to j can be found in O(|P|) time, where |P| is the number of edges in P. It is pointed out that the parallel algorithm can be updated properly to calculate the transitive closure of G and some graph algorithms can be derived from above computations. The ways to parallelize these derived graph algorithms in known parallelizing techniques are also given.
一般社団法人情報処理学会の論文
1994-07-15