Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916894173298688 |
|---|---|
| author | Barenboim, Leonid Goldenberg, Uri |
| author_facet | Barenboim, Leonid Goldenberg, Uri |
| contents | We obtain improved distributed algorithms in the CONGEST message-passing setting for problems on power graphs of an input graph $G$. This includes Coloring, Maximal Independent Set, and related problems. We develop a general deterministic technique that transforms R-round algorithms for $G$ with certain properties into $O(R \cdot Δ^{k/2 - 1})$-round algorithms for $G^k$. This improves the previously-known running time for such transformation, which was $O(R \cdot Δ^{k - 1})$. Consequently, for problems that can be solved by algorithms with the required properties and within polylogarithmic number of rounds, we obtain {quadratic} improvement for $G^k$ and {exponential} improvement for $G^2$. We also obtain significant improvements for problems with larger number of rounds in $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_04358 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model Barenboim, Leonid Goldenberg, Uri Distributed, Parallel, and Cluster Computing We obtain improved distributed algorithms in the CONGEST message-passing setting for problems on power graphs of an input graph $G$. This includes Coloring, Maximal Independent Set, and related problems. We develop a general deterministic technique that transforms R-round algorithms for $G$ with certain properties into $O(R \cdot Δ^{k/2 - 1})$-round algorithms for $G^k$. This improves the previously-known running time for such transformation, which was $O(R \cdot Δ^{k - 1})$. Consequently, for problems that can be solved by algorithms with the required properties and within polylogarithmic number of rounds, we obtain {quadratic} improvement for $G^k$ and {exponential} improvement for $G^2$. We also obtain significant improvements for problems with larger number of rounds in $G$. |
| title | Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2305.04358 |