{"ID":2834742,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.02252","arxiv_id":"2512.02252","title":"Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting","abstract":"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.","short_abstract":"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 pr...","url_abs":"https://arxiv.org/abs/2512.02252","url_pdf":"https://arxiv.org/pdf/2512.02252v2","authors":"[\"Adam Ganczorz\",\"Tomasz Jurdzinski\"]","published":"2025-12-01T22:47:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}