Multiple message broadcasting in communication networks

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.