Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww 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 array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are 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 to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.

Efficient parallel algorithms for some graph theory problems

In this paper, a sequential algorithm computing the all vertex pair distance matrixD and the path matrixP is given. On a PRAM EREW model withp,1≤p≤n ², 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 arrayA ^* of an undirected graph. The time complexity of the parallel algorithm isO (n ³/p). IfD, P andA ^* are 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 to search for a directed cycle with the minimum (maximum) length in a directed graph can all be solved inO (n ²/p+logp) time. Research supported by the Science Foundation of Shandong Province.