License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.34
URN: urn:nbn:de:0030-drops-131128
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13112/
Go to the corresponding LIPIcs Volume Portal

Ghaffari, Mohsen ; Grunau, Christoph ; Jin, Ce

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

pdf-format:
LIPIcs-DISC-2020-34.pdf (0.6 MB)

Abstract

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].

BibTeX - Entry

@InProceedings{ghaffari_et_al:LIPIcs:2020:13112,
  author =	{Mohsen Ghaffari and Christoph Grunau and Ce Jin},
  title =	{{Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13112},
  URN =		{urn:nbn:de:0030-drops-131128},
  doi =		{10.4230/LIPIcs.DISC.2020.34},
  annote =	{Keywords: Massively Parallel Computation, MIS, Matching, Coloring}
}

Keywords: Massively Parallel Computation, MIS, Matching, Coloring
Collection: 34th International Symposium on Distributed Computing (DISC 2020)
Issue Date: 2020
Date of publication: 07.10.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI