mwang@watmath.UUCP (mwang) (09/05/84)
Posted: Wed Sep 5 13:36:08 1984
Date-Received: Thu, 6-Sep-84 04:14:34 EDT
Expires: Sat, 8-Sep-84 00:00:00 EDT
Organization: U of Waterloo, Ontario
Lines: 36
_D_E_P_A_R_T_M_E_N_T _O_F _C_O_M_P_U_T_E_R _S_C_I_E_N_C_E
_U_N_I_V_E_R_S_I_T_Y _O_F _W_A_T_E_R_L_O_O
_S_E_M_I_N_A_R _A_C_T_I_V_I_T_I_E_S
_T_H_E_O_R_Y _S_E_M_I_N_A_R
- Friday, September 7, 1984.
Prof. S. Zaks of Technion, Israel (currently visiting
Carleton University), will speak on ``Tight Lower and
Upper Bounds for Distributed Algorithms for a Complete
Network of Processors.''
TIME: 10:30 AM
ROOM: MC 5097
ABSTRACT
Distributed algorithms for a complete network of pro-
cessors are discussed. We show:
(1) $ O ( n log n )$ lower and upper bounds for the
number of messages required by any algorithm that
finds a leader or a spanning tree,
(2) $ O ( n sup 2 ) $ such bounds for any algorithm
that finds a Hamiltonian path or a maximum match-
ing, and
(3) the problem of finding a minimum spanning tree is
harder than finding a spanning tree in such a net-
work.
September 5, 1984