Publisher DOI: 10.1016/j.tcs.2020.09.020
Title: A distributed algorithm for finding Hamiltonian cycles in random graphs in O(log⁡n) 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=(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.
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

Page view(s)

139
Last Week
0
Last month
5
checked on May 31, 2023

Google ScholarTM

Check

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.