Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks

Shingo OMURA; Hua ZHENG; Koichi WADA

doi:10.1093/ietisy/e88-d.1.89

Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks

Shingo OMURA, Hua ZHENG, Koichi WADA

Full Text Views

0

Share
Cite this

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

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.89-95

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.1.89

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Shingo OMURA, Hua ZHENG, Koichi WADA, "Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 1, pp. 89-95, January 2005, doi: 10.1093/ietisy/e88-d.1.89.
Abstract: 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 5log₂(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-1 vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.89/_p

Copy

@ARTICLE{e88-d_1_89,
author={Shingo OMURA, Hua ZHENG, Koichi WADA, },
journal={IEICE TRANSACTIONS on Information},
title={Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks},
year={2005},
volume={E88-D},
number={1},
pages={89-95},
abstract={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 5log₂(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-1 vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.},
keywords={},
doi={10.1093/ietisy/e88-d.1.89},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks
T2 - IEICE TRANSACTIONS on Information
SP - 89
EP - 95
AU - Shingo OMURA
AU - Hua ZHENG
AU - Koichi WADA
PY - 2005
DO - 10.1093/ietisy/e88-d.1.89
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - 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 5log₂(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-1 vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.
ER -