An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability
Rajko Nenadov, Angelika Steger, Pascal Su · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.