🚀 go-pugleaf

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.