Parallel transitive closure and transitive reduction algorithms
P. Chang, Lawrence J. Henschen · 2002
The authors provide distinct algorithms for computing transitive closure and transitive reduction with sequential time complexities of O( Sigma e/sub i/) and O(n/sup 2/+ Sigma e/sub i/), respectively, and parallel time complexities of O(e/sub i/) And O(n+e/sub i/), respectively. The proposed transitive closure algorithms are favorable for the sparse digraphs. It is still open whether transitive reduction may be computed in O( Sigma e/sub i/) (or O(e/sub i/) in parallel).>