Next: Definitions and Properties of
Up: The Technion Period (1986-94)
Previous: On Completeness and Soundness
The main result is a linear (in the number of edges) lower bound
on the (message) complexity of broadcast in the standard
point-to-point network model.
Comments:
Authored by B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish. Appeared in
- Jour. of the ACM, Vol. 37, No. 2, April 1990, pp. 238-256.
Oded Goldreich
2003-07-30