A distributed algorithm for finding Hamiltonian cycles in random graphs in O (logn) time

摘要

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) = (log n + log log n omega(n))/n. The determination of a concrete Hamiltonian cycle for G(n, p) is a nontrivial task, even when p is much larger than p(crit). In this paper we consider random graphs G(n, p) with p in (Omega) over tilde (1/root n), where (Omega) over tilde. 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 (logn) rounds. The algorithm works in the synchronous model and uses messages of size O (logn) and O (logn) memory per node. (C) 2020 Elsevier B.V. All rights reserved.