cs.DS math.CO
An O(n) time algorithm for finding Hamilton cycles with high probability. We design a randomized algorithm that finds a Hamilton cycle in mathcal O (n) time with high probability in a random graph G n,p with edge probability p ge C log n n . This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.