Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utcsrgv.UUCP
Path: utzoo!utcsrgv!phyllis
From: phyllis@utcsrgv.UUCP (Phyllis Eve Bregman)
Newsgroups: ont.events
Subject: Zaks: "Tight lower and upper bounds for distributed algorithms..."
Message-ID: <3882@utcsrgv.UUCP>
Date: Thu, 12-Apr-84 18:23:11 EST
Article-I.D.: utcsrgv.3882
Posted: Thu Apr 12 18:23:11 1984
Date-Received: Thu, 12-Apr-84 20:23:08 EST
Organization: CSRG, University of Toronto
Lines: 28

****

      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