LINE BROADCASTING IN CYCLES

Broadcasting is the process of transmitting information from an origin ating node (processor) in a network to all other nodes in the network. A local broadcast scheme only allows a node to send information along single communication links to adjacent nodes, while a line broadcast scheme allows nodes to use paths of several communication links to cal l distant nodes. The minimum time possible for broadcasting in a netwo rk of n nodes when no node is involved in more than one communication at any given time is [log n] phases. Local broadcasting is not suffici ent, in general, for broadcasting to be completed in minimum time; lin e broadcasting is always sufficient. An optimal line broadcast is a mi nimum-time broadcast that uses the smallest possible total number of c ommunication links. In this paper, we give a complete characterization of optimal line broadcasting in cycles, and we develop efficient meth ods for constructing optimal line broadcast schemes. (C) 1998 Elsevier Science B.V. All rights reserved.