Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs
Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs
复制标题
随机图中哈密顿循环和生成树的最优并行构造
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Q. Stout
中科院分区：
文献类型：
--
作者：
P. MacKenzie;Q. Stout
我们在涉及随机图的某些问题的平行复杂性上给出了紧密的界限，我们表明，汉密尔顿周期，宽阔的第一个跨越树，并且可以在〜（log”（log'n）中构建最大匹配log* n处理器上的crcw pram上是对最佳先前算法的实质性改进，该算法需要 @（（log log n）2）时间和n log2 n处理器。来自其邻接矩阵的随机图的边缘盖需要Q（log'N）带有O（n）处理器的CRCW婴儿车的预期时间。匹配，因此所有这些问题的下限都表明我们的算法仅是这种新的下限技术。这些问题的下限。
We give tight bounds on the parallel complexity of some problems involving random graphs. Specifically, we show that a Hamiltonian cycle, a breadth first spanning tree, and a maximal matching can all be constructed in ~(log” n) expected time using n/ log* n processors on the CRCW PRAM. This is a substantial improvement over the best previous algorithms, which required @((log log n)2) time and n log2 n processors. We then introduce a technique which allows us to prove that constructing an edge cover of a random graph from its adjacency matrix requires Q(log’ n) expected time on a CRCW PRAM with O(n) processors. Constructing an edge cover is implicit in constructing a spanning tree, a Hamiltonian cycle, and a maximal matching, so this lower bound holds for all these problems, showing that our algorithms are ontimal. This new lower bound techniaue is one . of the very few lower bound techniques known which apply to randomized CRCW PRAM algorithms, and it provides the first nontrivial parallel lower bounds for these problems.