Optimal Neighborhood Broadcast in Star Graphs

S. Fujita (Japan)

Keywords

communication algorithm, multicast, singleport model, star graph.

Abstract

In this paper, we consider the problem of construct ing a multicast tree in star interconnection networks under the single-port communication model. Unlike previous schemes for constructing space-efficient mul ticast trees, we adopt the completion time of each mul ticast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme of log2 n + O( log n) time units for the star graph of dimension n.

Important Links:



Go Back