An efficient parallel algorithm for the transitive closure of a graph
We give a vectorial and parallel algorithm that performs the transitive closure of a directed graph in an average O(n^2 log n) operations using an improved breadth-first method. The vectorization problem solved here gives a good example of methods efficient for graph problems. Computation on CDC CYBER 205 has proved very efficient.