A Distributed algorithm to find Hamiltonian cycles in Gnp random graphs

In this paper, we present a distributed algorithm to find Hamiltonian cycles in random binomial graphs Gnp. The algorithm works on a synchronous distributed setting by first creating a small cycle, then covering almost all vertices in the graph with several disjoint paths, and finally patching these paths and the uncovered vertices to the cycle. Our analysis shows that, with high probability, our algorithm is able to find a Hamiltonian cycle in Gnp when p_n=omega(sqrt{log n}/n^{1/4}). Moreover, we conduct an average case complexity analysis that shows that our algorithm terminates in expected sub-linear time, namely in O(n^{3/4+epsilon}) pulses.Postprint (published version