Title :
Parallel transitive closure and transitive reduction algorithms
Author :
Chang, Pintsang ; Henschen, Lawrence J.
Author_Institution :
Rockwell Int. Corp., Downers Grove, IL, USA
Abstract :
The authors provide distinct algorithms for computing transitive closure and transitive reduction with sequential time complexities of O(Σei) and O(n2+Σei), respectively, and parallel time complexities of O(ei) And O(n +ei), respectively. The proposed transitive closure algorithms are favorable for the sparse digraphs. It is still open whether transitive reduction may be computed in O(Σe i) (or O(ei) in parallel)
Keywords :
database theory; relational databases; distinct algorithms; parallel time complexities; parallel transitive closure algorithms; sequential time complexities; sparse digraphs; transitive reduction algorithms; Algebra; Concurrent computing; Data structures; Deductive databases; Inverse problems; Iterative algorithms; Parallel processing; Query processing; Sparse matrices; Switching systems;
Conference_Titel :
Databases, Parallel Architectures and Their Applications,. PARBASE-90, International Conference on
Conference_Location :
Miami Beach, FL
Print_ISBN :
0-8186-2035-8
DOI :
10.1109/PARBSE.1990.77136
