Publisher DOI: | 10.1016/j.tcs.2020.09.020 | Title: | A distributed algorithm for finding Hamiltonian cycles in random graphs in O(logn) time | Language: | English | Authors: | Turau, Volker | Keywords: | Distributed algorithm; Hamiltonian cycle; Random graph | Issue Date: | Dec-2020 | Source: | Theoretical Computer Science 846: 61-74 (2020-12) | Abstract (english): | 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. |
URI: | http://hdl.handle.net/11420/7416 | ISSN: | 0304-3975 | Journal: | Theoretical computer science | Institute: | Telematik E-17 | Document Type: | Article | Project: | Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken |
Appears in Collections: | Publications without fulltext |
Show full item record
Add Files to Item
Note about this record
Cite this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.