PARALLEL ALGORITHMS FOR THE HAMILTONIAN CYCLE AND HAMILTONIAN PATH PROBLEMS IN SEMICOMPLETE BIPARTITE DIGRAPHS

We give an O (log(4) n)-time O(n(2))-processor CRCW PRAM algorithm to find a hamiltonian cycle in a strong semicomplete bipartite digraph, B , provided that a factor of B (i.e., a collection of vertex disjoint c ycles covering the vertex set of B)is computed in a preprocessing step . The factor is found (if it exists) using a bipartite matching algori thm, hence placing the whole algorithm in the class Random-NC. We show that any parallel algorithm which can check the existence of a hamilt onian cycle in a strong semicomplete bipartite digraph in time O(r(n)) using p(n) processors can be used to check the existence of a perfect matching in a bipartite graph in time O(r(n) + n(2)/p(n)) using p(n) processors. Hence, our problem belongs to the class NC if and only if perfect matching in bipartite graphs belongs to NC. We also consider t he problem of finding a hamiltonian path in a semicomplete bipartite d igraph.