文章基本信息

标题：Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
本地全文：下载
作者：Mohsen Ghaffari ; Christoph Grunau ; Ce Jin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-18
DOI：10.4230/LIPIcs.DISC.2020.34
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 coloring trees with a constant number of colors. 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Â²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].
关键词：Massively Parallel Computation; MIS; Matching; Coloring