Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in \(O(\log n)\) Time
verfasst von : Volker Turau
Erschienen in: Structural Information and Communication Complexity
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \(p_{crit}= (\log n + \log \log n + \omega _n)/n\). 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 \(\tilde{\varOmega }(1/\sqrt{n})\), where \(\tilde{\varOmega }\) hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm \(\mathcal{A}_\mathsf {HC}\) 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.