Abstract of An Efficient Parallel NC Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs

An Efficient Parallel NC Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs

Authors: Martin Furer and Balaji Raghavachari.

Journal:Journal of Algorithms, Volume 18, pages 203-220, 1995.

Abstract. 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**3 n) time on a CREW PRAM.