Induced Broadcasting Algorithms in Iterated Line Digraphs

We propose broadcasting algorithms for line digraphs in the telephone model. The new protocols use a broadcasting protocol for a graph G to obtain a broadcasting protocol for the graph L k (G), the graph obtained by applying k times, the line digraph operation to G. As a consequence improved bounds for the broadcasting time in De Bruijn, Kautz and Wrapped Butterfly digraphs are obtained. 1 Introduction Considerable attention has been recently devoted to the dissemination of information in parallel computing, since the time needed to disseminate information among the processors in a network often determines the running time the whole algorithm. Broadcasting is the process in which a node of the network (the originator) sends one piece of information to all members of the network by placing calls over the communication lines of the network. This is to be completed as quickly as possible subject to the constraints of the considered model. This problem has been widely studied both f..