Conditionally Optimal Parallel Coloring of Forests

Christoph Grunau*, Rustam Latypov*, Yannic Maus*, Shreyas Pai*, Jara Uitto*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

10 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko37th International Symposium on Distributed Computing, DISC 2023
ToimittajatRotem Oshman
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroninen)978-3-95977-301-0
DOI - pysyväislinkit
TilaJulkaistu - lokak. 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Symposium on Distributed Computing - L'Aquila, Italia
Kesto: 10 lokak. 202312 lokak. 2023
Konferenssinumero: 37

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
Vuosikerta281
ISSN (painettu)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC
Maa/AlueItalia
KaupunkiL'Aquila
Ajanjakso10/10/202312/10/2023

Sormenjälki

Sukella tutkimusaiheisiin 'Conditionally Optimal Parallel Coloring of Forests'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä