Adaptive Massively Parallel Connectivity in Optimal Space

Rustam Latypov, Jakub Łacki, Yannic Maus, Jara Uitto

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

9 Lataukset (Pure)

Abstrakti

We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log∗n) rounds in forests (with high probability) and 2O(log∗n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using I(m + n log(k) n) total space in expectation (in each round), where k is an arbitrarily large constant and log(k) is the k-th iterate of the log2 function. This improves upon existing algorithms requiring ω(m + n log n) total space.

AlkuperäiskieliEnglanti
OtsikkoSPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
KustantajaACM
Sivut431-441
Sivumäärä11
ISBN (elektroninen)978-1-4503-9545-8
DOI - pysyväislinkit
TilaJulkaistu - 17 kesäk. 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaAnnual ACM Symposium on Parallelism in Algorithms and Architectures - Orlando, Yhdysvallat
Kesto: 17 kesäk. 202319 kesäk. 2023
Konferenssinumero: 35

Conference

ConferenceAnnual ACM Symposium on Parallelism in Algorithms and Architectures
LyhennettäSPAA
Maa/AlueYhdysvallat
KaupunkiOrlando
Ajanjakso17/06/202319/06/2023

Sormenjälki

Sukella tutkimusaiheisiin 'Adaptive Massively Parallel Connectivity in Optimal Space'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä