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 | URI: | http://hdl.handle.net/11420/2601 | 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)
171
Last Week
1
1
Last month
3
3
checked on May 31, 2023
SCOPUSTM
Citations
2
Last Week
0
0
Last month
0
0
checked on Jun 30, 2022
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.