Loading...
Please wait, while we are loading the content...
Similar Documents
Tight bounds on minimum broadcast networks (1991)
| Content Provider | CiteSeerX |
|---|---|
| Author | Grigni, Michelangelo David Peleg, Y. |
| 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 dlg ne, 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. We show B(n) = (L(n) n) and D(n) = (lg lg n+L(n)), and for every n we give a con-struction simultaneously within a constant factor of both lower bounds. For all n we also construct graphs with O(n) edges and O(lg lg n) maxdegree requiring at most dlg ne +1 time units to broadcast. Our broadcast protocols may be implemented with local control and O(lg lg n) bits overhead per message. |
| File Format | |
| Volume Number | 4 |
| Journal | SIAM J. Discrete Math |
| Language | English |
| Publisher Date | 1991-01-01 |
| Access Restriction | Open |
| Subject Keyword | Minimum Broadcast Network Lg Lg Broadcast Graph Time Unit Broadcast Protocol Local Control Tight Bound Minimum Number Time Step N-vertex Communication Network Message Transmission Minimum Maxdegree Constant Factor Binary Representation Optimal Time Dlg Ne |
| Content Type | Text |
| Resource Type | Article |
