Adaptive Massively Parallel Connectivity in Optimal Space
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Author
Latypov, Rustam
Łacki, Jakub
Maus, Yannic
Uitto, Jara
Date
2023-06-17
Major/Subject
Mcode
Degree programme
Language
en
Pages
11
431-441
431-441
Series
SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
Abstract
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.Description
Funding Information: Supported by the Academy of Finland, Grant 334238 Publisher Copyright: © 2023 Owner/Author.
Keywords
adaptive massively parallel model, ampc, connectivity
Other note
Citation
Latypov , R , Łacki , J , Maus , Y & Uitto , J 2023 , Adaptive Massively Parallel Connectivity in Optimal Space . in SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures . ACM , pp. 431-441 , Annual ACM Symposium on Parallelism in Algorithms and Architectures , Orlando , Florida , United States , 17/06/2023 . https://doi.org/10.1145/3558481.3591103
