Design of optimal systolic algorithms for the transitive closure problem
Dilip Sarkar, Amar Mukherjee · IEEE Transactions on Computers · 1992
New optimal systolic algorithms for the transitive closure problem on ring and linear arrays of processors is presented. The data dependency of the Warshal-Floyd algorithm is exploited to obtain highly pipelined parallel algorithms. One of the algorithms is asymptotically seven times more cost-effective than previous algorithms for computing transitive closure problems. The authors introduce a new expository device, called the RCT diagram, that depicts simultaneously the flow of data and computation of parallel algorithms.>