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 G(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)~(1/2)/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.