Options
A distributed algorithm for finding Hamiltonian cycles in random graphs in O(logn) time
Publikationstyp
Journal Article
Date Issued
2020-12
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
846
Start Page
61
End Page
74
Citation
Theoretical Computer Science 846: 61-74 (2020-12)
Publisher DOI
Scopus ID
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 pcrit=(logn+loglogn+ω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(logn) rounds. The algorithm works in the synchronous model and uses messages of size O(logn) and O(logn) memory per node.
Subjects
Distributed algorithm
Hamiltonian cycle
Random graph