Turau, VolkerVolkerTurau2019-05-022019-05-022018International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018)http://hdl.handle.net/11420/2601It 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 (formula presented). The determination of a concrete Hamiltonian cycle is even for values much larger than p crit a nontrivial task. In this paper we consider random graphs G(n, p) with p in (formula presented), where (formula presented) 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.enInformatikA distributed algorithm for finding hamiltonian cycles in random graphs in O(Log n) timeConference Paper10.1007/978-3-030-01325-7_11Other