Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks(<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

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

• 社団法人電子情報通信学会の論文
• 2005-01-01

著者

• Wada Koichi

  The Department Of Computer Science And Engineering Graduate School Of Engineering Nagoya Institute O

• ZHENG Hua

  the Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute

• OMURA Shingo

  the Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute

• Zheng Hua

  The Department Of Computer Science And Engineering Graduate School Of Engineering Nagoya Institute O

• Omura Shingo

  The Department Of Computer Science And Engineering Graduate School Of Engineering Nagoya Institute O

関連論文

• Parallel Algorithms for Convex Hull Problems and Their Paradigm(Special Issue on Algorithm Engineering : Surveys)
• An Approximation Algorithm for Minimum Certificate Dispersal Problems (Graphs and Networks)
• An Optimal Certificate Dispersal Algorithm for Mobile Ad Hoc Networks(Discrete Mathematics and Its Applications)
• Neighborhood Broadcasting in Undirected de Bruijn and Kautz Networks(Foundations of Computer Science)

スポンサーリンク