A successful algorithm for the undirected Hamiltonian path problem (Q1061488)

In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes. It first reintroduces the concepts described by the authors in Oper. Res. Lett. 3, 35-42 (1984; Zbl 0531.90092), and then explains the algorithm. Computational comparison with the algorithm by \textit{L. Posa} [Discrete Math. 14, 359- 364 (1976; Zbl 0322.05127)] is given. It is shown that a Hamiltonian Path is a spanning arborescence with zero ramification index. Given an undirected graph, the Minram algorithm starts by finding a spanning tree which defines a unique spanning arborescence. By suitable pivots it locates a locally minimal value of the ramification index. If this local minima corresponds to zero ramification index then the algorithm is considered to have ended successfully, else a failure is reported. Computational performance of the algorithm on randomly generated Hamiltonian graphs is given. Comparison with our version of the Posa algorithm which we call Posa-ran algorithm is also made.