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

Page view(s)

6
Last Week
1
Last month
checked on May 19, 2019

Google ScholarTM

Check

Export

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