1991/05/01 by Michelangelo Grigni, David Peleg · 85 citations
Computer Science · Mathematics · #Combinatorics #Computer science #Cooperative Communication and Network Coding #Discrete mathematics #Graph #Integer (computer science) #Interconnection Networks and Systems #Mathematics #Mobile Ad Hoc Networks #Upper and lower bounds #Vertex (graph theory)
paper · doi:10.1137/0404021
published in SIAM Journal on Discrete Mathematics 4(2), 207-222 (Society for Industrial and Applied Mathematics)
openalex publication_date 1991/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
A broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time \lceil \lg n\rceil, 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 ) = Θ ( \lg \lg 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( \lg \lg n ) maxdegree requiring at most \lceil \lg n \rceil + 1 time units to broadcast are constructed. These broadcast protocols may be implemented with local control and O( \lg \lg n ) bits overhead per message.