Expected Computation Time for Hamiltonian Path Problem - Gurevich, Yuri; Shelah, Saharon (Journal on Computing, 1987)
Let G(n,p) be a random graph with n vertices and the edge probability p. We give an algorithm for Hamiltonian Path Problem whose expected run-time on G(n,p) is cn/p + o(n) for any fixed p. This is the best possible result for the case of fixed p. The expected run-time of a slighty modified version of the algorithm remains polynomial if p = p(n) > n-c where c is positive and small. The paper is based on a 1984 technical report.