***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Vijay V. Vazirani (University of California, Irvine)

Thursday 1st November, 3:00 in Fine Hall 224.

Title: A theory of alternating paths and blossoms, from the perspective of minimum length

It is well known that the proof of some prominent results in mathematics took a
very long time --- decades and even centuries. The first proof of the
Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in
general graphs, was recently completed --- over four decades after the
publication of the algorithm (1980). MV is still the most efficient known
algorithm for the problem. In contrast, spectacular progress in the field of
combinatorial optimization has led to improved running times for most other
fundamental problems in the last three decades, including bipartite matching and
max-flow.

The new ideas contained in the MV algorithm and its proof remain largely
unknown, and hence unexplored; we hope to rectify that shortcoming.
We will assume at least a rudimentary understanding of non-bipartite matching. 


		----------------------------------


Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)