论文标题
改进了MIS，匹配和着色的MPC算法
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
论文作者
论文摘要
我们提出$ O（\ log \ log n）$圆形可扩展性的可扩展性平行计算算法，用于最大独立集和最大匹配，在树木和更一般的有界支流的图形以及恒定着色树的图形。遵循标准，通过可扩展的MPC算法，我们的意思是，对于任何正常常数$Δ<1 $，这些算法可以在具有容量/内存小至$ n^δ$的机器上工作。我们的结果比Behnezhad等人的$ O（\ log^2 \ log n）$圆算法改善。 [PODC'19]。此外，我们的匹配算法大概是最佳的，因为它的界限匹配了$ω（\ log \ log n）$条件的下限Ghaffari，Kuhn和Uitto [focs'19]。
We present $O(\log\log n)$ round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded arboricity, as well as for constant coloring trees. Following the standards, by a scalable MPC algorithm, we mean that these algorithms can work on machines that have capacity/memory as small as $n^δ$ for any positive constant $δ<1$. Our results improve over the $O(\log^2\log n)$ round algorithms of Behnezhad et al. [PODC'19]. Moreover, our matching algorithm is presumably optimal as its bound matches an $Ω(\log\log n)$ conditional lower bound of Ghaffari, Kuhn, and Uitto [FOCS'19].
