A distributed algorithm for finding hamiltonian cycles in random graphs in O(Log n) time

Publikationstyp
Conference Paper
Date Issued
2018
Sprache
English
Author(s)
Turau, Volker  
Institut
Telematik E-17  
TORE-URI
http://hdl.handle.net/11420/2601
First published in
Lecture notes in computer science  
Number in series
11085 LNCS
Start Page
72
End Page
87
Citation
International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018)
Contribution to Conference
International Colloquium on Structural Information and Communication Complexity, SIROCCO 2018  
Publisher DOI
10.1007/978-3-030-01325-7_11
Scopus ID
2-s2.0-85056467156
Publisher
Springer
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 (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.
DDC Class
004: Informatik