Log-time multicast to local vertices in the star graph
Satoshi Fujita · 2002
In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast 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 for the star graph of dimension n in 1.3125 log/sub 2/ n+O(log log n) time units, that is at most 1.3125 times of a trivial lower bound.