Carnegie Mellon University
file.pdf (483.63 kB)

An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

Download (483.63 kB)
journal contribution
posted 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.


Publisher Statement

This is the accepted version of the article which has been published in final form at



Usage metrics