Finding a Hamilton cycle fast on average using rotations and extensions. Issue 1 (16th March 2020) - Alon, Yahav; Krivelevich, Michael
Abstract : 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 p = p ( n ) ≥ 70 n − 1 2 . This improves upon previous results on this problem due to Gurevich and Shelah, and to Thomason.