We present new implementations of BSP/CGM algorithms for the Transitive Closure Problem. Our strategies deal with size of the message and communication rounds, problems that cause inefficiency in the implementations of the transitive closure algorithms. The algorithms were implemented using LAM/MP1 in two Beowulfs. The implementation results show the efficiency and scalability of the presented algorithms, improve the previous results and compare favorably with other parallel implementations. Besides we show that the presented algorithms can be used to solve real problems.
展开▼
