Decentralized Distributed Graph Coloring: Cluster Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908407437459456 |
|---|---|
| author | Flin, Maxime Halldorsson, Magnus M. Nolin, Alexandre |
| author_facet | Flin, Maxime Halldorsson, Magnus M. Nolin, Alexandre |
| contents | Graph coloring is fundamental to distributed computing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the underlying communication network by contracting nodes and edges, and they appear frequently as components in the study of distributed algorithms. In particular, we give a $O(\log^* n)$-round algorithm to $(Δ+1)$-color cluster graphs of at least polylogarithmic degree. The previous best bound known was $\operatorname{poly}(\log n)$ [Flin et al., SODA'24]. This properly generalizes results in the CONGEST model and shows that distributed graph problems can be solved quickly even when the node itself is decentralized. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07725 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Decentralized Distributed Graph Coloring: Cluster Graphs Flin, Maxime Halldorsson, Magnus M. Nolin, Alexandre Distributed, Parallel, and Cluster Computing Data Structures and Algorithms F.2.2 Graph coloring is fundamental to distributed computing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the underlying communication network by contracting nodes and edges, and they appear frequently as components in the study of distributed algorithms. In particular, we give a $O(\log^* n)$-round algorithm to $(Δ+1)$-color cluster graphs of at least polylogarithmic degree. The previous best bound known was $\operatorname{poly}(\log n)$ [Flin et al., SODA'24]. This properly generalizes results in the CONGEST model and shows that distributed graph problems can be solved quickly even when the node itself is decentralized. |
| title | Decentralized Distributed Graph Coloring: Cluster Graphs |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2405.07725 |