Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks

Shingo OMURA  Hua ZHENG  Koichi WADA  

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

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


Summary: 
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.