A PARALLEL REDUCTION OF HAMILTONIAN CYCLE TO HAMILTONIAN PATH IN TOURNAMENTS

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamilto nian paths. The running time of our algorithm is O(log n) using O(n(2) /log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW P RAM using O(n(2)/log n log log n) processors. As a corollary, we obtai n a new parallel algorithm for computing Hamiltonian cycles in tournam ents. This algorithm can be implemented in time O(log n) using O(n(2)/ log n) processors in the CRCW model and in time O(log(2) n) with O(n(2 )/log n log log n) processors in the EREW model. (C) 1995 Academic Pre ss, Inc.