TY - CONF
AB - 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.
AU - Anastos, Michael
ID - 12432
SN - 0272-5428
T2 - 63rd Annual IEEE Symposium on Foundations of Computer Science
TI - Solving the Hamilton cycle problem fast on average
VL - 2022-October
ER -