For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks
Shingo OMURA Hua ZHENG Koichi WADA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
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.