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: V.V. Vazirani:  "Maximum matchings without tears:  A randomizing algorithm".
Message-ID: <3636@utcsrgv.UUCP>
Date: Wed, 28-Mar-84 11:18:38 EST
Article-I.D.: utcsrgv.3636
Posted: Wed Mar 28 11:18:38 1984
Date-Received: Wed, 28-Mar-84 12:30:54 EST
Organization: CSRG, University of Toronto
Lines: 31

[****]

      UofT Department of Computer Science Seminar Schedule for
		the week of March 26th, 1984

Friday, March 30th, 1:00 P.M., GB304:  Dr. Vijay V. Vazirani,
   Harvard University, Cambridge, MA.:  "Maximum matchings without
   tears:  A randomizing algorithm".

   ABSTRACT:  Even though efficient algorithms have been discovered for
   finding maximum matchings in general graphs (the best running time
   being 0(sqrt(V) E, all of the known polynomial time algorithms for
   this problem tend to be conceptually involved and difficult to
   program.

   We give a 0(V**3.5) randomizing algorithm for the maximum matching
   problem, based on a new approach.  Whereas the conventional
   algorithms find maximum matchings by finding 'blossoms' and
   'augmenting paths', our algorithm is based on finding the rank and
   the inverse (over a finite field) or certain matrices obtained from
   the adjacency matrix of the given graph.  We also give efficient
   randomizing algorithms for finding the rank and inverse of matrices
   over a finite field.  Our algorithms are conceptually simple and
   easy to program.  Furthermore, our techniques may yield a fast
   parallel algorithm for the Maximum Matching problem.
-- 
		Phyllis Eve Bregman
		CSRG, Univ. of Toronto
		{decvax,linus,ihnp4,uw-beaver,allegra,utzoo}!utcsrgv!phyllis
		CSNET:  phyllis@toronto
		(416) 978 6985