ANTEPENULTIMATE BROADCASTING

Broadcasting is an information dissemination problem in which informat ion originating at one node of a communication network (modeled as a g raph) must be transmitted to all other nodes as quickly as possible. A broadcast graph is a graph which permits broadcasting from any origin ator in minimum time. In this paper, we present new methods for constr ucting sparse broadcast graphs. Our constructions are based on graph c ompounding operations which are relative to Vertex sets with certain p roperties that depend on the broadcast protocols of the graphs. We sho w that many previous methods for constructing sparse broadcast graphs are special cases of our methods. We demonstrate our constructions by producing new sparse broadcast graphs and by showing how many previous ly constructed graphs can be obtained in a systematic way. (C) 1995 Jo hn Wiley & Sons, Inc.