A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time
A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time
复制标题
一种在 O(log n) 时间内查找随机图中哈密顿循环的分布式算法
DOI：
10.1007/978-3-030-01325-7_11
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
V. Turau
中科院分区：
文献类型：
--
作者：
V. Turau
已知一个随机图G（n，p）当p大于临界值p c r i t=（log n+ log n+ ω n）/n时，包含whp个Hamilton圈.确定G（n，p）的具体Hamilton圈是一个非平凡的任务，即使当p远大于pcrit时也是如此。本文考虑随机图G（n，p），其中p在Ω <$（1/n）中，Ω <$隐藏n中的多对数因子.对于这个范围内的p，我们提出了一个分布式算法A HC，发现whp在O（log n）轮的哈密顿循环。该算法工作在同步模型中，每个节点使用的消息大小为O（log n），内存为O（log n）。
It is known for some time that a random graph G (n, p) contains whp a Hamiltonian cycle if p is larger than the critical value p c r i t=(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 p c r i t. 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 A HC that finds whp 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.
登录
查看更多内容
一种在随机图中查找哈密顿循环的分布式算法
DOI：
--
发表时间：
2004
期刊：
Combinatorial and Algorithmic Aspects of Networking
影响因子：
--
作者：
Eythan Levy;G. Louchard;Jordi Petit
通讯作者：
Jordi Petit
虚拟环路由趋势
DOI：
--
发表时间：
2009
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
D. Malkhi;S. Sen;Kunal Talwar;Renato F. Werneck;Udi Wieder
通讯作者：
Udi Wieder
随机图中哈密顿循环和生成树的最优并行构造
DOI：
--
发表时间：
1993
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
P. MacKenzie;Q. Stout
通讯作者：
Q. Stout
随机图中哈密顿环的快速高效分布式计算
DOI：
10.1109/icdcs.2018.00079
发表时间：
2018
期刊：
38th IEEE International Conference on Distributed Computing Systems (ICDCS
影响因子：
--
作者：
Chatterjee, Soumyottam;Fathi, Reza;Pandurangan, Gopal;Pham, Nguyen Dinh
通讯作者：
Pham, Nguyen Dinh
有多少条随机边使图具有哈密顿性？
DOI：
--
发表时间：
1983
期刊：
Comb.
影响因子：
--
作者：
Eli Shamir
通讯作者：
Eli Shamir