LCS Publication Details
Publication Title: TIGHT BOUNDS ON MINIMUM BROADCAST NETWORKS
Publication Author: Grigni, Michelangelo
Additional Authors: Peleg, David
LCS Document Number: MIT-LCS-TM-374
Publication Date: 10-1-1988
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
A broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time [lg 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.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.