subramon@iris.eecs.ucdavis.edu (Ramesh Subramonian) (06/25/91)
We designed an algorithm for Transitive Closure that runs on an Asynchronous PRAM that has a Theta(n*n*n log n) work bound using up to n*n*n processors. It appeared in the 1990 ICPP as "Asynchronous algorithms for list ranking and transitive closure" by Charles Martel and Ramesh Subramonian ramesh From: Jeffrey D. Ullman <ullman@theory.stanford.edu> Mihalis Yannakakis and I had a paper in the 2nd SPAA conference. ---jdu From: sun@cs.nthu.edu.tw (mr794312) Hi ! I have got a PHD dissertation of department of computer science and information engineering of national taiwan university. The author solved the transitive closure problem of undirected graph in O(1) time. The model he used is a processor arrays with reconfigurable bus systems. The title of this dissertation is "Reconfigurational Computation : A New Algorithm Design Strategy on Processor Arrays with Reconfigurable Bus Systems", advisor is Gen-Huey Chen, student is Biing-Feng Wang. Sun, Wei-tsung sun@cs.nthu.edu.tw Other References I compiled Greenberg, Albert. G and Michael J. Fischer " On Computing Weak transitive closure in O(log n) expected random parallel time " proceedings of the 1982 International Conference on Parallel Processing (ICPP 82), pp. 199-204. Guh, K and J. Chavarria " A Parallel Processing Strategy for Computing the Transitive Closure of a Database relation " Parbase-90 Conference on Databases, Parallel Architectures and Their Applications, Miami Beach, 1990. Kumar, V.K. Prasanna and Yu-Chen Tsai , " Mapping two dimensional Systolic Arrays to One dimensional Arrays and Applications " Proceedings of ICPP 1988, Vol. 1, Architecture, pp 39- 46. Lee, PeiZong and Zvi M. Kedem " On High-speed Computing with a Programmable Linear Array" Proceedings of Supercomputing 88, pp 425-432, IEEE, and ACM Sigarch, Nov. 1988. Moreno, Jaime H and Tomas Lang " Graph-based partitioning of Matrix Algorithms for Systolic Arrays : Applications to Transitive Closure" ICPP 1988, Vol. 1, Architecture, pp 28-31. Nunez, F. J and N. Torralba " Transitive Closure Partitioning and Its Mapping to a Systolic Array" proceedings of ICPP 1987, pp 564-566. Vanscoy, L. Frances " The parallel recognition of Classes of Graphs" IEEE Transactions on Computers, Vol. C-29, No. 7, pp 563-570, July 1980. Varman, P. J. and I.V. Ramakrishnan " Dynamic programming and transitive Closure on Linear pipelines" Proceedings of ICPP 1984, pp 359-364. Additional Comment The book by Joseph Ja Ja on Introduction to Parallel Algorithms also talks about Transitive Closure. -Srinivas Kankanahalli Dept. of Computer Science West Virginia University.