|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
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.3KB)
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.
|
|
