Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks

摘要

This paper considers a neighborhood broadcasting protocol in undirected de Bruijn and Kautz networks. The neighborhood broadcasting problem(NBP) is the problem of disseminating a message from an originator vertex to only its neighbors. Our protocol works under the single-port and half-duplex model and solves NBP in 5 log_2(n + 1) + O(1) time units on the undirected de Bruijn graph UB(n, d) with n~d vertices and the undirected Kautz graph UK(n, d) with n~d+n~(d-1) vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.