A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time
share
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 p_crit= ( n + n + ω_n)/n. 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 Ω̃(1/√(n)), where Ω̃ 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( n) rounds. The algorithm works in the synchronous model and uses messages of size O( n) and O( n) memory per node.
READ FULL TEXT