Efficient Broadcasting Protocols . . .

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. This is to be completed as quickly as possible subject to the constraints that each call involves only two vertices, each call requires one unit of time, a vertex can participate in only one call per unit of time, and a vertex can only call a vertex to which it is adjacent. The determination of the broadcast time has been done for several networks. Here we give new protocols which improve the known results for the de Bruijn network. The ideas can also be used for similar networks; we give as example the case of the Kautz network