ALCOMFT-TR-03-82

Eythan Levy, Guy Louchard and Jordi Petit
A distributed algorithm to find Hamiltonian cycles in G_n,p random graphs
Barcelona. Work packages 2 and 4. November 2003.

Abstract: In this paper, we present a distributed algorithm to find Hamiltonian cycles in random binomial graphs G(n,p_n). 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 G(n,p_n) 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.

Postscript file: ALCOMFT-TR-03-82.ps.gz (205 kb).