A distributed algorithm to find Hamiltonian cycles in G(n, p) random graphs

In this paper, we present a distributed algorithm to find Hamiltonian cycles in C/(n, p) graphs. The algorithm works in a synchronous distributed setting. It finds a Hamiltonian cycle in G(n, p) with high probability when p = ω √/log n/n 1/4), and terminates in linear worst-case number of pulses, and in expected O(n 3/4+∈) pulses. The algorithm requires, in each node of the network, only O(n) space and O(n) internal instructions. © Springer-Verlag Berlin Heidelberg 2005.SCOPUS: cp.p