phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (04/13/84)
**** UofT Department of Computer Science Seminar Schedule for the week of April 16th, 1984 Wednesday, April 18th, 4:00 P.M., SF3202 Professor Shmuel Zaks, Laboratory for Computer Science, M.I.T.: "Tight lower and upper bounds for distributed algorithms for a complete network of processors". ABSTRACT: Distributed algorithms for a complete network of n processors are discussed. We show: 1. 0(nlogn) lower and upper bounds for the number of messages required by any algorithm that finds a leading or a spanning tree. 2. 0(nsup2) such bounds for any algorithm that finds a Hamiltonian path or a maximum matching, and 3. that finding a minimum spanning tree is harder than finding a spanning tree in such a network. -- Phyllis Eve Bregman CSRG, Univ. of Toronto {decvax,linus,ihnp4,uw-beaver,allegra,utzoo}!utcsrgv!phyllis CSNET: phyllis@toronto (416) 978 6985