Hierarchical broadcast and gossip networks

In this paper, we study hierarchical broadcast (respectively gossip) networks. These networks are such that every connected induced subgraph is also a broadcast (respectively gossip) network. This study follows and generalizes the study of hierarchical broadcast networks in the undirected case (cf. Fraigniaud, 1998). Here, we study broadcasting in the directed case, while gossiping is studied in the unit cost as well as the linear cost model. We prove that, for any of these three models, the minimum outdegree (respectively degree) of a directed hierarchical broadcast network (respectively hierarchical gossip network, hierarchical linear gossip network) of order n is equal to n - 2. (C) 2000 Elsevier Science B.V. All rights reserved.