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.
| Original language | English |
|---|---|
| Title of host publication | SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures |
| Publisher | Association of Computing Machinery |
| Pages | 431-441 |
| Number of pages | 11 |
| ISBN (Electronic) | 9781450395458 |
| DOIs | |
| Publication status | Published - 17 Jun 2023 |
| Event | 35th ACM Symposium on Parallelism in Algorithms and Architectures: SPAA 2023 - Orlando, United States Duration: 17 Jun 2023 → 19 Jun 2023 |
Conference
| Conference | 35th ACM Symposium on Parallelism in Algorithms and Architectures |
|---|---|
| Abbreviated title | SPAA 2023 |
| Country/Territory | United States |
| City | Orlando |
| Period | 17/06/23 → 19/06/23 |
Keywords
- adaptive massively parallel model
- ampc
- connectivity
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture