An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three1. Issue 1 (10th April 2014) - Frieze, Alan; Haber, Simi
Abstract We describe an algorithm for finding Hamilton cycles in random graphs. Our model is the random graph <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqs7bp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G=Gn, mδ≥3</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqs794" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(n1+o(1))</alternatives> time and succeeds w.h.p. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 73–98, 2015