Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914178195783680 |
|---|---|
| author | Ganczorz, Adam Jurdzinski, Tomasz |
| author_facet | Ganczorz, Adam Jurdzinski, Tomasz |
| contents | We consider basic communication tasks in arbitrary radio networks: $k$-broadcasting and $k$-gathering. In the case of $k$-broadcasting messages from $k$ sources have to get to all nodes in the network. The goal of $k$-gathering is to collect messages from $k$ source nodes in a designated sink node. We consider these problems in the framework of distributed algorithms with advice. Krisko and Miller showed in 2021 that the optimal size of advice for $k$-broadcasting is $Θ(\min(\log Δ,$ $ \log k))$, where $Δ$ is equal to the maximum degree of a vertex of the input communication graph. We show that the same bound $Θ(\min(\log Δ, \log k))$ on the size of optimal labeling scheme holds also for the $k$-gathering problems. Moreover, we design fast algorithms for both problems with asymptotically optimal size of advice. For $k$-gathering our algorithm works in at most $D+k$ rounds, where $D$ is the diameter of the communication graph. This time bound is optimal even for centralized algorithms. We apply the $k$-gathering algorithm for $k$-broadcasting to achieve an algorithm working in time $O(D+\log^2 n+k)$ rounds. We also exhibit a logarithmic time complexity gap between distributed algorithms with advice of optimal size and distributed algorithms with distinct arbitrary labels. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02252 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting Ganczorz, Adam Jurdzinski, Tomasz Data Structures and Algorithms We consider basic communication tasks in arbitrary radio networks: $k$-broadcasting and $k$-gathering. In the case of $k$-broadcasting messages from $k$ sources have to get to all nodes in the network. The goal of $k$-gathering is to collect messages from $k$ source nodes in a designated sink node. We consider these problems in the framework of distributed algorithms with advice. Krisko and Miller showed in 2021 that the optimal size of advice for $k$-broadcasting is $Θ(\min(\log Δ,$ $ \log k))$, where $Δ$ is equal to the maximum degree of a vertex of the input communication graph. We show that the same bound $Θ(\min(\log Δ, \log k))$ on the size of optimal labeling scheme holds also for the $k$-gathering problems. Moreover, we design fast algorithms for both problems with asymptotically optimal size of advice. For $k$-gathering our algorithm works in at most $D+k$ rounds, where $D$ is the diameter of the communication graph. This time bound is optimal even for centralized algorithms. We apply the $k$-gathering algorithm for $k$-broadcasting to achieve an algorithm working in time $O(D+\log^2 n+k)$ rounds. We also exhibit a logarithmic time complexity gap between distributed algorithms with advice of optimal size and distributed algorithms with distinct arbitrary labels. |
| title | Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.02252 |