Efficient Parallel Algorithms for Some Graph Theory Problems

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 the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(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 undirec…