Abstract

Broadcasting is a basic problem of communication in usual networks. To design an optimal broadcast network on n nodes is very difficult. Numerous previous papers have investigated ways to construct networks with sparse communication lines in which broadcasting can be completed in the theoretically minimum amount of time from any originator. Minimum broadcast networks are the sparsest possible networks of this type, which have the minimum number of communication lines denoted by B ( n ). Many previous papers also have investigated the construction of minimum broadcast networks for small values of n . Among those, a minimum broadcast network on 63 nodes is the largest. In this thesis, a new technique of constructing broadcast networks on 2 p - 1 nodes is introduced. Furthermore, this technique is improved to construct broadcast networks on any odd number of nodes. Improved upper bounds on B ( n ) for broadcast networks on 2 p - 1 nodes are presented. Also, general bounds on B ( n ) for broadcast networks on any odd number of nodes are given. Finally, all known minimum broadcast networks on 2 p - 1 nodes are studied and common properties of them are observed. Then, careful studies of the observed properties and massive experimental work lead to the construction of a minimum broadcast network on 127 nodes. This network is proven to have 389 communication lines.