Almost-Tight Distributed Minimum Cut Algorithms
Almost-Tight Distributed Minimum Cut Algorithms
复制标题
近紧分布式最小割算法
DOI：
10.1007/978-3-662-45174-8_30
复制
发表时间：
2014
影响因子：
--
通讯作者：
Hsin
中科院分区：
文献类型：
--
作者：
Danupon Nanongkai;Hsin
我们研究在加权分布式消息传递网络（CONGEST模型）中计算最小割的问题。设λ为最小割，n为网络中的节点（处理器）数量，D为网络直径。我们的算法能够在\(O((\sqrt{n} \log^{*} n +D)\lambda^4 \log^2 n)\)时间内精确计算出λ。据我们所知，这是第一篇明确研究在分布式环境下计算精确最小割的论文。此前，由于普里查德（Pritchard）和图里梅拉（Thurimella）用于计算2 - 边连通和3 - 边连通分量的\(O(D)\)时间和\(O(D + n^{1/2}\log^{*} n)\)时间算法，对于此问题的非平凡次线性时间算法仅在λ ≤ 3且为无权图时已知[《ACM算法汇刊》2011年]。
We study the problem of computing the minimum cut in a weighted distributed message-passing networks (the CONGEST model). Let λ be the minimum cut, n be the number of nodes (processors) in the network, and D be the network diameter. Our algorithm can compute λ exactly in \(O((\sqrt{n} \log^{*} n +D)\lambda^4 \log^2 n)\) time. To the best of our knowledge, this is the first paper that explicitly studies computing the exact minimum cut in the distributed setting. Previously, non-trivial sublinear time algorithms for this problem are known only for unweighted graphs when λ ≤ 3 due to Pritchard and Thurimella’s O(D)-time and O(D + n 1/2log* n)-time algorithms for computing 2-edge-connected and 3-edge-connected components [ACM Transactions on Algorithms 2011].