论文标题
确定性的统治集大规模并行算法
Deterministic Massively Parallel Algorithms for Ruling Sets
论文作者
论文摘要
在本文中，我们提出了一个确定性$ O（\ log \ log n）$ - 在具有$ \ tilde {o}（n）$ memory的大规模并行计算模型中的2条集合问题中，圆形算法；该算法还以$ o（\ log \ log n）$ rounds在拥挤的集团模型中运行。这比这些模型的最快已知的确定性2式设置算法的速度要快，这仅仅是$ o（\logδ）$ - 圆形确定性最大独立集算法，这是由于Czumaj，Davies和Parter引起的（SPAA 2020）。我们的结果是通过将Kothapalli和Pemmaraju的2条集合算法取代（FSTTCS 2012）获得的。
In this paper we present a deterministic $O(\log\log n)$-round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with $\tilde{O}(n)$ memory; this algorithm also runs in $O(\log\log n)$ rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the $O(\log Δ)$-round deterministic Maximal Independent Set algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).
