Compound Constructions of Minimal Broadcast Networks

Abstract

Compound methods have been shown to be very effective in the construction of minimal broadcast networks (mbns). Compound methods generate a large mbn by combining multiple copies of an mbn G using the structure of another mbn H. Node deletion is also allowed in some of these methods. The subset of connecting nodes of G has been desined as solid h-cover by Bermond, Fraigniaud and Peters, and center node set by Weng and Ventura. This article shows that the two concepts are equivalent. We also provide new properties for center node sets, including bounds on the minimum size of a center node set, show how to reduce the number of center nodes of an mbn generated by a compound method, and propose an iterative compounding algorithm that generates the sparsest known mbns in many cases.