  We study the Hamilton cycle problem with input a random graph G=G(n,p) in two
settings. In the first one, G is given to us in the form of randomly ordered
adjacency lists while in the second one we are given the adjacency matrix of G.
In each of the settings we give a deterministic algorithm that w.h.p. either it
finds a Hamilton cycle or it returns a certificate that such a cycle does not
exists, for p > 0. The running times of our algorithms are w.h.p. O(n) and
O(n/p) respectively each being best possible in its own setting.
