Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks(<Special Section>Foundations of Computer Science)

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-l> vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.