Finding a Hamilton cycle fast on average using rotations and extensions
Yahav Alon, Michael Krivelevich · Random Structures and Algorithms · 2020
We present an algorithm CRE, which either finds a Hamilton cycle in a graph G or determines that there is no such cycle in the graph. The algorithm's expected running time over input distribution G∼G(n,p) is (1+o(1))n/p, the optimal possible expected time, for . This improves upon previous results on this problem due to Gurevich and Shelah, and to Thomason.