The Complexity of Determining Existence a Hamiltonian Cycle is $O(n^3)$

Abstract

The Hamiltonian cycle problem in digraph is mapped into a matching cover bipartite graph. Based on this mapping, it is proved that determining existence a Hamiltonian cycle in graph is $O(n^3)$.

arXiv comment6 papers

References in corpus (2)

• A note on minimal matching covered graphs
• The Complexity of HCP in Digraps with Degree Bound Two