2025/12/01 by Ganczorz, Adam, Jurdzinski, Tomasz
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2512.02252
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+log2 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.