Minimal-Time k -Line Broadcasting
Iris Gaber · SIAM Journal on Discrete Mathematics · 2005
Broadcasting refers to the process of sending a message from a source to an entire communication network. Line broadcasting (defined by Farley [Networks, 10 (1980), pp. 59--70]) assumes that members may "switch-through" any number of calls during a time unit. Namely, two members of the network may communicate with each other through a path as long as no link is involved in more than one call at the same time unit. Two paths may intersect, during a given time unit, only in vertices. A generalization of that model is the k-line-broadcasting model, which has the same properties as the line-broadcasting model with the additional constraint that the distance between two communicating members is at most k. The parameters to the problem are the network, the originator, and k. In this paper we generalize Farley's algorithm into the k-line-broadcasting model. An algorithm is presented which produces a k-line-broadcasting scheme for any given tree and source vertex which consumes $O({D\over k}+\log_2 n)$ time units, where n is the number of vertices and D is the distance of the furthest vertex from the originator. This asymptotically achieves the lower bound provided.