Tight Bounds on Mimimum Broadcast Networks

A broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time n, given that each message transmission takes one time unit and a vertex participates in at most one transmission per time step. This paper establishes tight bounds for $B( n )$, the minimum number of edges of a broadcast graph, and $D( n )$, the minimum maxdegree of a broadcast graph. Let $L( n )$ denote the number of consecutive leading 1’s in the binary representation of integer $n - 1$. It is shown that B( n ) = Θ ( L( n )· n ) and D( n ) = Θ ( n + L ( n ) ) and for every n we give a construction simultaneously within a constant factor of both lower bounds. For all n, graphs with $O( n )$ edges and O( n ) maxdegree requiring at most n + 1 time units to broadcast are constructed. These broadcast protocols may be implemented with local control and O( n ) bits overhead per message.