|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||Source:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (11085): 72-87 (2018)||Journal or Series Name:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)||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.||URI:||http://hdl.handle.net/11420/2601||ISBN:||978-303001324-0||ISSN:||0302-9743||Institute:||Telematik E-17||Type:||InProceedings (Aufsatz / Paper einer Konferenz etc.)|
|Appears in Collections:||Publications without fulltext|
Show full item record
checked on May 19, 2019
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.