Parallel algorithms for the transitive closure and the connected component problems

ABSTRACT

Parallel programs are presented that determine the transitive closure of a matrix using n3 processors and connected components of an undirected graph using n2 processors. In both cases, the desired results are obtained in time 0(log2n). It is assumed that the processors have access to common memory. Simultaneous access to the same location is permitted for fetch, but not store, instructions. The problem of determining the connected components of a graph using a parallel computer has recently appeared in the literature [1,2]. The result in [1] is based on finding the transitive closure of a matrix in time 0(log2n) which can be done using 0(n3) processors. We show that n2 processors are sufficient to solve the connected component problem in time 0(log2n). We present algorithm CLOSURE that will find the transitive closure of Boolean matrix M [n by n] using n3 processors [numbered P(0,0,0) through P(n−1 ,n−1, n−1)] each of which has local memory and each of which can access common array A [n by n].

REFERENCES

• 1: Arjomandi E. and D.G. Corneil. Parallel Computations in Graph Theory. Proceedings of the 16th Annual Symposium on Foundations of Computer Science (October 1975).
• 2: K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972 [doi>10.1145/361573.361576]
• 3: Ullman J.D. private communication.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory