Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond

Mohsen Ghaffari, Christoph Grunau, Ce Jin

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…