An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
journal contributionposted on 2013-12-20, 00:00 authored by Alan FriezeAlan Frieze, Simi Haber
We describe an algorithm for finding Hamilton cycles in random graphs. Our model is the random graph . In this model G is drawn uniformly from graphs with vertex set [n], m edges and minimum degree at least three. We focus on the case where m = cn for constant c. If c is sufficiently large then our algorithm runs in time and succeeds w.h.p.