@inproceedings{12432,
abstract = {We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥
100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and
Krivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n
−1/2 respectively.},
author = {Anastos, Michael},
booktitle = {63rd Annual IEEE Symposium on Foundations of Computer Science},
isbn = {9781665455190},
issn = {0272-5428},
location = {Denver, CO, United States},
pages = {919--930},
publisher = {Institute of Electrical and Electronics Engineers},
title = {{Solving the Hamilton cycle problem fast on average}},
doi = {10.1109/FOCS54457.2022.00091},
volume = {2022-October},
year = {2022},
}