An O(n) time algorithm for finding Hamilton cycles with high probability
We design a randomized algorithm that finds a Hamilton cycle in šŖ(n) time with high probability in a random graph G_n,p with edge probability pā„ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.
READ FULL TEXT