MULTIPLE MESSAGE BROADCASTING IN COMMUNICATION-NETWORKS

Broadcasting refers to the process of dissemination of a set of messag es originating from one node to all other nodes in a communication net work. We assume that, at any given time, a node can transmit a message along at most one incident link and simultaneously receive a message along at most one incident link. We first present an algorithm for det ermining the amount of time needed to broadcast k messages in an arbit rary tree. Second, we show that, for every n, there exists a graph wit h n nodes whose k-message broadcast time matches the trivial lower bou nd [log n] + k - 1 by designing a broadcast scheme for complete graphs . We call those graphs minimal broadcast graphs. Finally, we construct an n node minimal broadcast graph with fewer than ([log n] + 1)2([log n]-1) edges. (C) 1995 John Wiley & Sons, Inc.