Broadcasting is the information dissemination process whereby a set of messages is transmitted from one member to all other members of a communication networks. On the communication model, it is assumed that the number of messages that can be transmitted and received by a processor at a unit time is at most one, respectively. And it is also assumed that transmitting a message from a processor to an adjacent processor requires one unit of time.
In this thesis, we first consider the tree type networks. We present an O(kn logn) time algorithm which determines the amount of time required to broadcast k messages from an arbitrary vertex to every other vertices in a tree with n vertices. Second, we give the lower bound of the time required to broadcast k messages from an arbitrary vertex in a graph with n vertices, and show that, for every n, there exists a graph satisfying such lower bound. We call such graph minimum time multiple message broadcast graph. Finally, we consider the problem of finding a minimum time multiple message broadcast graph with relatively small number of edges. We present a class of graph with O(n logn) edges which is minimum time multiple message broadcast graph.
