Open access
Datum
2023-10Typ
- Conference Paper
ETH Bibliographie
yes
Altmetrics
Abstract
We show the first conditionally optimal deterministic algorithm for 3-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in O(log log n) rounds and uses optimal global space. The best previous algorithm requires 4 colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic. Our main technical contribution is an O(log log n)-round algorithm to compute a partition of the forest into O(log n) ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000640121Publikationsstatus
publishedExterne Links
Herausgeber(in)
Buchtitel
37th International Symposium on Distributed Computing (DISC 2023)Zeitschrift / Serie
Leibniz International Proceedings in Informatics (LIPIcs)Band
Seiten / Artikelnummer
Verlag
Schloss Dagstuhl - Leibniz-Zentrum für InformatikKonferenz
Thema
Theory of computation; Massively parallel algorithms; Massively parallel computation; Coloring; Forests; OptimalOrganisationseinheit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Zugehörige Publikationen und Daten
Is new version of: https://doi.org/10.48550/arXiv.2308.00355
ETH Bibliographie
yes
Altmetrics