论文部分内容阅读
In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the pathmatrix Pis given.On a PRAM EREW model with p,1≤p≤n~2,processors,a parallel version of thesequential algorithm is shown.This method can also be used to get a parallel algorithm to computetransitive closure arrayof an undirected graph.The time complexify of the parallel algorithm isO(n~3/p).If D,P andare known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and tosearch for a directed cycle with the minimum(maximum)length in a directed graph can all be solvedin O(n~2/p~+ logp)time.
In this paper, a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given. On a PRAM EREW model with p, 1 ≦ p ≦ n ~ 2, processors, a parallel version of these sequence algorithms is shown.This method can also be used to get a parallel algorithm to compute transitive closure array of an undirected graph. The time complexify of the parallel algorithm isO (n ~ 3 / p) .If D, P andare known, it is shown that the problem to find all connected components, to compute the diameter of an undirected graph, to determine the center of a directed graph and tosearch for a directed cycle with the minimum (maximum) length in a directed graph can all be solved in O (n ~ 2 / p ~ + logp ) time.