Bounded depth broadcasting Original Research Article

Broadcasting is an information dissemination problem in which messages originating at one site of an information network (modelled as a graph) must be transmitted to all other sites as quickly as possible. In this paper we study broadcasting in networks in which information degenerates with each transmission, so there is a limit on the number of times information can be retransmitted before it becomes unusable. We prove lower and upper bounds on the time to broadcast in this setting and on the minimum number of communication links necessary to permit minimum time broadcasting from any originator. We present several general constructions that produce infinite families of optimal networks (minimum time and minimum number of communication links). We also exhibit a number of small optimal networks that are not produced by the general constructions.