Mini-course "The matching problem". Lecture 2 (Stephen Fenner)

803 views · Published 24 June 2017 · 1:14:00 · Indexed 1 November 2026

Channel: ФКН ВШЭ · 2017 · Education

Watch on YouTube

The matching problem in graphs is central to graph theory and combinatorics, with a host of related problems and connections. In this minicourse, we will discuss historical approaches to this problem, including Koenig's Minimax theorem (which ties together several results, including the Marriage theorem and Hall's theorem), as well as the problem's connection to matrix determinants, network flows and cuts, matroids (time permitting) and geometry (such as the matching polytope). 

We will review fast sequential algorithms for matching, including the reduction to max flow for bipartite graphs and Edmonds's algorithm for matching in general graphs. Finally, we look at newer ways to parallelize matching algorithms, including the Isolation lemma and its use in finding fast, randomized parallel algorithms for matching, and new geometry-based ways to partially derandomize these algorithms.

Lecturer: Stephen Fenner, University of South Carolina.

Faculty of Computer Science: https://cs.hse.ru/en/
Follow us: https://www.facebook.com/hsefcs; https://twitter.com/CS_HSE

More from this channel