file.pdf (483.63 kB)
Download file

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 20.12.2013, 00:00 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.

History

Publisher Statement

This is the accepted version of the article which has been published in final form at http://dx.doi.org/10.1002/rsa.20542

Date

20/12/2013

Usage metrics

Exports