A distributed algorithm for finding hamiltonian cycles in random graphs in O(Log n) time

Abstract

It is known for some time that a random graph G(n, p) contains w.h.p. a Hamiltonian cycle if p is larger than the critical value (formula presented). The determination of a concrete Hamiltonian cycle is even for values much larger than p crit a nontrivial task. In this paper we consider random graphs G(n, p) with p in (formula presented), where (formula presented) hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm A HC that finds w.h.p. a Hamiltonian cycle in O(logn) rounds. The algorithm works in the synchronous model and uses messages of size O(logn) and O(logn) memory per node.