Finding a Hamilton cycle fast on average using rotations and extensions. Issue 1 (16th March 2020)

• Record Type: Journal Article
• Authors: Alon, Yahav; Krivelevich, Michael
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 32
• Page End: 46
• Publication Date: 2020-03-16
• Subjects: Hamilton cycles -- random graphs -- expected polynomial time algorithms; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20918
• Languages: English
• ISSNs: 1042-9832

Abstract

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.