BOUNDED DEPTH BROADCASTING

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