phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (03/28/84)
[****]
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