A Novel Edge-Efficiency-Based Algorithm for Hamiltonian Cycle and Path Detection in Graphs

Abstract

Searching for the existence of a Hamiltonian cycle and path connecting all nodes in a graph is an NP-complete problem. This article proposes the E2 Algorithm for constructing the Hamiltonian cycle in an arbitrary graph without edges’ weights. The Kmax and Kmin that are particular spanning trees are generated first to obtain the fundamental cuts. Then, each edge's total number in the fundamental cuts is obtained to state edge efficiency. Next, all nodes are navigated with a method that determines priority, starting with the highest degree node at the most efficient edge. Thus, when the greedy traversal succeeds, a Hamiltonian cycle or path is constructed between all nodes. Since E² is a deterministic greedy algorithm without backtracking, it does not guarantee finding a Hamiltonian cycle in every Hamiltonian graph; however, it always terminates in polynomial time. These methods are used for the first time to obtain the Hamiltonian cycle in this study. In addition, we present an object-oriented construction to avoid getting exponential algorithm complexity. Finally, to prove the correctness of the method, we show whether some general graphs are Hamiltonian using the proposed method.