Low-Diameter Graph Decomposition Is in NC

Low-Diameter Graph Decomposition Is in NC
复制标题

小直径图分解在 NC 中

DOI：
--
复制
发表时间：
1992
期刊：
Random Struct. Algorithms
影响因子：
--
通讯作者：
D. Peleg
D. Peleg
中科院分区：
--
文献类型：
--
作者：
B. Awerbuch;B. Berger;L. Cowen;D. Peleg

文献摘要

被引文献

相似文献

我们获得了第一个针对任意图上的低直径图分解问题的确定性 NC 算法。我们通过对 Linial 和 Saks 算法进行去随机化来实现这一目标。我们的算法运行时间为 O(log5(n))，并使用 O(n2) 个处理器。
We obtain the first deterministic NC algorithm for the lowdiameter graph decomposition problem on arbitrary graphs. We achieve this through derandomizing an algorithm of Linial and Saks. Our algorithm runs in O(log5(n)) time and uses O(n2) processors.