We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\geq n^{1+\epsilon}$ for any constant $\epsilon>0$, our algorithm requires $O(m \log n)$ work and $O(\log^3 n)$ depth and succeeds with high probability. Its work matches the best $O(m \log n)$ runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by $O(\log^3 n)$ factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.
翻译：我们为非扭曲的图表展示了第一个工作-最佳多元数深平行算法。 对于$m\geq n ⁇ 1 ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ }$m\epsilon>0$, 我们的算法需要$O( m\log n) work and $O( log}}3 n) 和$O( log} 3 n) 的深度, 并且极有可能成功。 它的工作与序列算法[ MON STOC 2020, GMW SOSA 20211] 的最佳运行时间相匹配。 这改善了Geissmann 和 Gianinazzi [SPA 2018] 之前的最佳工作, 以 $(\\log}3 n) $ 来改善它们的算法深度。 为此, 我们设计了一种工作效率近似算算算法, 并同时使用最近的序列算法 [MN STOC 2020; GMW SOSA 20211], 它利用了两个尊重最小切值和二维或多维范围之间的连接 。
相关内容
微信扫码咨询专知VIP会员