Premium
Finding a Hamilton cycle fast on average using rotations and extensions
Author(s) -
Alon Yahav,
Krivelevich Michael
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20918
Subject(s) - graph , hamiltonian path , running time , combinatorics , mathematics , algorithm , computer science
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.