Fast probabilistic algorithms for hamiltonian circuits and matchings

Abstract

We describe and analyse three simple efficient algorithms with good probabilistic behaviour; two algorithms with run times of O(n(log n)2) which almost certainly find directed (undirected) Hamiltonian circuits in random graphs of at least cn log n edges, and an algorithm with a run time of O(n log n) which almost certainly finds a perfect matching in a random graph of at least cn log n edges. Auxiliary propositions regarding conversion between input distributions and the "de-randomization" of randomized algorithms are proved. A new model, the random access computer (RAC), is introduced specifically to treat run times in low-level complexity.