Publisher DOI: 10.1007/978-3-030-01325-7_11
Title: A distributed algorithm for finding hamiltonian cycles in random graphs in O(Log n) time
Language: English
Authors: Turau, Volker 
Issue Date: 2018
Publisher: Springer
Source: International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018)
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 (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.
Conference: International Colloquium on Structural Information and Communication Complexity, SIROCCO 2018 
ISBN: 978-303001324-0
ISSN: 0302-9743
Institute: Telematik E-17 
Document Type: Chapter/Article (Proceedings)
Project: Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken 
Fehlertolerante verteilte Algorithmen 
Part of Series: Lecture notes in computer science 
Volume number: 11085 LNCS
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on May 31, 2023


Last Week
Last month
checked on Jun 30, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.