Distributed Triangle Detection via Expander Decomposition
Distributed Triangle Detection via Expander Decomposition
复制标题
通过扩展器分解进行分布式三角形检测
DOI：
10.1137/1.9781611975482.51
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zhang, H.
中科院分区：
文献类型：
--
作者：
Chang, Y.-J.;Pettie, S.;Zhang, H.
我们提出了改进的分布式三角形检测算法及其在 CONGEST 模型中的变体。我们证明三角形检测、计数和枚举可以在 Õ(n1/2) 轮中解决。相比之下，由于 Izumi 和 LeGall (PODC 2017)，三角形检测和枚举之前最先进的界限分别为 Õ(n2/3) 和 Õ(n3/4)。 这项工作的主要技术新颖性是分布式图分区算法。我们证明，在 Õ(n1–δ) 轮中，我们可以将网络 G= (V, E) 的边集划分为三部分 E=Em∪Es∪Er，使得由 Em 引起的每个连通分量具有最小度 Ω(nδ) 和电导 Ω(1/polylog(n))。因此，组件内随机游走的混合时间为 O(polylog(n))。E 诱导的子图最多具有 nδ。|Er| ≤ |E|/6。我们所有的算法都基于以下通用框架，我们相信这超出了这项工作的范围。粗略地说，我们处理 setEsby 一种对于低树度图有效的算法，并处理 setErusing 递归调用。对于由 Em 引起的每个连接组件，我们能够通过应用 Ghaffari、Kuhn 和 Su (PODC 2017) 的路由算法来以较小的开销模拟 CONGESTED-CLIQUE 算法，以实现高电导图。
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved inÕ(n1/2) rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration wereÕ(n2/3) andÕ(n3/4), respectively, due to Izumi and LeGall (PODC 2017).The main technical novelty in this work is a distributed graph partitioning algorithm. We show that inÕ(n1–δ) rounds we can partition the edge set of the networkG= (V, E) into three partsE=Em∪Es∪Ersuch thatEach connected component induced byEmhas minimum degreeΩ(nδ) and conductance Ω(1/polylog(n)). As a consequence the mixing time of a random walk within the component isO(polylog(n)).The subgraph induced byEshas arboricity at mostnδ.|Er| ≤ |E|/6.All of our algorithms are based on the following generic framework, which we believe is of interest beyond this work. Roughly, we deal with the setEsby an algorithm that is efficient for low-arboricity graphs, and deal with the setErusing recursive calls. For each connected component induced byEm, we are able to simulate CONGESTED-CLIQUE algorithms with small overhead by applying a routing algorithm due to Ghaffari, Kuhn, and Su (PODC 2017) for high conductance graphs.
登录
查看更多内容
广播 CONGEST 中的确定性子图检测
DOI：
--
发表时间：
2017
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
Janne H. Korhonen;Joel Rybicki
通讯作者：
Joel Rybicki
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
DOI：
10.1145/3087801.3087827
发表时间：
2017-07
期刊：
Proceedings of the ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su
通讯作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su
平面网络的分布式算法 I：平面嵌入
DOI：
10.1145/2933057.2933109
发表时间：
2016
期刊：
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
M. Ghaffari;Bernhard Haeupler
通讯作者：
Bernhard Haeupler
分布式稀疏割逼近
DOI：
--
发表时间：
2015
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
F. Kuhn;A. R. Molla
通讯作者：
A. R. Molla