An O(n) time algorithm for finding Hamilton cycles with high probability

Rajko Nenadov, Angelika Steger, Pascal Su

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$. T…