[ont.events] Zaks: "Tight lower and upper bounds for distributed algorithms..."

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