Deterministic Subgraph Detection in Broadcast CONGEST
Deterministic Subgraph Detection in Broadcast CONGEST
复制标题
广播 CONGEST 中的确定性子图检测
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Joel Rybicki
中科院分区：
文献类型：
--
作者：
Janne H. Korhonen;Joel Rybicki
我们提出了简单的确定性算法的子图发现和枚举的广播CONGEST模型的分布式计算：
对于任何常数$k$，检测$k $路径和$k$节点上的树可以在$O（1）$轮内完成。
对于任何常数$k$，检测$k$-循环和$k$节点上的伪树可以在$O（n）$轮中完成。
--在$d$-退化图上，团和$4$-圈可以在$O（d + log n）$轮中枚举，而$5$-圈可以在$O（d^2 + log n）$轮中枚举。
在许多情况下，这些界限紧到对数因子。此外，我们证明了$d$-退化图的算法可以改进到最佳复杂度$O（d/log n）$和$O（d^2/log n）$，分别在支持的CONGEST模型，它可以被看作是一个中间模型之间的CONGEST和拥塞团。
We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation:
-- For any constant $k$, detecting $k$-paths and trees on $k$ nodes can be done in $O(1)$ rounds.
-- For any constant $k$, detecting $k$-cycles and pseudotrees on $k$ nodes can be done in $O(n)$ rounds.
-- On $d$-degenerate graphs, cliques and $4$-cycles can be enumerated in $O(d + log n)$ rounds, and $5$-cycles in $O(d^2 + log n)$ rounds.
In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for $d$-degenerate graphs can be improved to optimal complexity $O(d/log n)$ and $O(d^2/log n)$, respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.
DOI：
10.1145/3210377.3210409
发表时间：
2016-02
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
通讯作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato