MULTIPLE MESSAGE BROADCASTING IN COMMUNICATION-NETWORKS

Abstract

Broadcasting refers to the process of dissemination of a set of messages originating from one node to all other nodes in a communication network. 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 determining the amount of time needed to broadcast k messages in an arbitrary tree. Second, we show that, for every n, there exists a graph with n nodes whose k-message broadcast time matches the trivial lower bound [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.