  We present CertifyHAM, an algorithm which takes as input a graph G and either
finds a Hamilton cycle of G or it outputs that such a cycle does not exists. If
G=G(n, p) and p >2000/n then the expected running time of CertifyHAM is O(n/p).
This improves upon previous results due to Gurevich and Shelah, Thomason and
Alon and Krivelevich.
