Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks

Shingo OMURA  Hua ZHENG  Koichi WADA  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.1   pp.89-95
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.1.89
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
neighborhood broadcast,  de Bruijn,  Kautz,  

Full Text: PDF(523.8KB)
>>Buy this Article

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 5log2(n+1) + O(1) time units on the undirected de Bruijn graph UB(n,d) with nd vertices and the undirected Kautz graph UK(n,d) with nd + nd-1 vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.