An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

<p>We describe an algorithm for finding Hamilton cycles in random graphs. Our model is the random graph . In this model <em>G</em> is drawn uniformly from graphs with vertex set [<em>n</em>], <em>m</em> edges and minimum degree at least three. We focus on the case where <em>m</em> = <em>cn</em> for constant <em>c</em>. If <em>c</em> is sufficiently large then our algorithm runs in time and succeeds w.h.p.