An Algorithm for Finding All Hamiltonian Cycles in Digraph via Hierarchical Correlation

The problem to find all Hamiltonian cycles in a digraph is NP-hard, and there isn't an efficient algorithm to find all Hamiltonian cycles in a digraph. The traditional algorithm for finding all Hamiltonian cycles in a digraph is not information search, and an algorithm is designed for improving the speed of finding all Hamiltonian cycles in a digraph. Correlation of path and hierarchical correlation of path based on the concept of path are built in digraph. Based on hierarchical correlation, an algorithm for finding all Hamiltonian cycles in digraph is designed. Path and correlation of path in which path's length is k+1 are obtained by using hierarchical correlation of path in which path's length is k in the algorithm designed, and step by step, k+1 becomes greater and greater. When k+1 is equal to n-1, all Hamiltonian paths are obtained, so all Hamiltonian cycles are found through checking all Hamiltonian paths. The algorithms analysis indicate that the designed algorithm is more efficient than the current algorithms for finding all Hamiltonian cycles in digraph, so complexity of the algorithm is reduced. A new train of thought for calculating the Hamiltonian cycle problem is provided.