Turau, VolkerVolkerTurau2020-09-292020-09-292020-12Theoretical Computer Science 846: 61-74 (2020-12)http://hdl.handle.net/11420/7416It 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 pcrit=(log⁡n+log⁡log⁡n+ωn)/n. The determination of a concrete Hamiltonian cycle for G(n,p) is a nontrivial task, even when p is much larger than pcrit. In this paper we consider random graphs G(n,p) with p in Ω˜(1/n), where Ω˜ hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm AHC that finds w.h.p. a Hamiltonian cycle in O(log⁡n) rounds. The algorithm works in the synchronous model and uses messages of size O(log⁡n) and O(log⁡n) memory per node.en0304-397520206174Distributed algorithmHamiltonian cycleRandom graphJournal Article10.1016/j.tcs.2020.09.020Other