A distributed algorithm for finding Hamiltonian cycles in random graphs in O(log⁡n) time

Publikationstyp
Journal Article
Date Issued
2020-12
Sprache
English
Author(s)
Turau, Volker  
Institut
Telematik E-17  
TORE-URI
http://hdl.handle.net/11420/7416
Journal
Theoretical computer science  
Volume
846
Start Page
61
End Page
74
Citation
Theoretical Computer Science 846: 61-74 (2020-12)
Publisher DOI
10.1016/j.tcs.2020.09.020
Scopus ID
2-s2.0-85091082435
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=(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.
Subjects
Distributed algorithm
Hamiltonian cycle
Random graph