An efficient parallel algorithm for finding hamiltonian cycles in dense directed graphs

Let G be a directed graph with n vertices such that whenever there is no arc from any vertex u to another vertex v, then the sum of the outdegree of u and the indegree of v is at least n. It is known that such a graph G always contains a Hamiltonian cycle. We show how to compute a Hamiltonian cycle of G with a linear number of processors in O(log³n) time on a CREW PRAM.