@article{gurevich1987expected,
author = {Gurevich, Yuri and Shelah, Saharon},
title = {Expected Computation Time for Hamiltonian Path Problem},
year = {1987},
month = {July},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/expected-computation-time-hamiltonian-path-problem/},
pages = {486-502},
journal = {Journal on Computing},
volume = {16},
number = {3},
}