Parallel Minimum Cuts in O ( m log 2 n ) Work and Low Depth
Parallel Minimum Cuts in O ( m log 2 n ) Work and Low Depth
复制标题
O ( m log 2 n ) 工作和低深度并行最小切削
DOI：
10.1145/3409964.3461797
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Blelloch, Guy E.
中科院分区：
文献类型：
--
作者：
Anderson, Daniel;Blelloch, Guy E.
我们提出了一种随机化（mlog2n）工作，O（polylogn）深度的最小切割并行算法。该算法与Gawrychowski、Mozes和Weimann [ICALP ' 20]最近提出的序列算法的工作边界相匹配，并改进了Geissmann和Gianinazzi [SPAA ' 18]先前最好的并行算法，该算法执行so （mlog4n）工作深度为o （polylogn）。我们的算法使用了三个可能相互独立的组件。首先，我们设计了一个并行数据结构，有效地支持对树的批量混合查询和更新。它推广和改进了Geissmann和Gianinazzi先前的数据结构的工作边界，并且相对于最佳序列算法具有较高的工作效率。其次，我们设计了一个近似最小割的并行算法，改进了Karger和Motwani之前的结果。我们使用这个算法给出了一个高效的过程来产生树填充，就像在最小切割的顺序算法中一样。最后，设计了一种求解最小2相切问题的高效并行算法。
We present a randomizedO(mlog2n) work,O(polylogn) depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP’20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA’18], which performsO(mlog4n) work inO(polylogn) depth.Our algorithm makes use of three components that might be of independent interest. First, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves the work bounds of a previous data structure of Geissmann and Gianinazzi and is work efficient with respect to the best sequential algorithm. Second, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger’s sequential algorithm for minimum cuts. Last, we design an efficient parallel algorithm for solving the minimum 2-respecting cut problem.