Minimum broadcast digraphs

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Numerous previous papers have investigated ways to construct sparse graphs (networks) in which this process can be completed in minimum time from any originator. In this paper, the authors consider the broadcasting problem in directed graphs. They show that several of the upper and lower bounds which have been produced for the undirected problem have analogs in the directed case. The authors describe several techniques to construct sparse digraphs on n vertices in which broadcasting can be completed in minimum time from any originator. For several values of n, these techniques produce the sparsest possible digraphs of this type (called minimum broadcast digraphs). For other values of n, these techniques produce the sparsest known digraphs of this type.