Simple Person's Applied Math Seminar (SPAMS)

Thursday, November 01, 2018 at 6:00pm to 7:00pm

Room 2-132

SPEAKER:   Vishesh Jain  (MIT)

TITLE:   Finding perfect matchings in regular bipartite graphs in O (n log n)  time


Hall's theorem shows that a d-regular bipartite graph on parts of size n always contains a perfect matching.  Such a perfect matching may be found quickly using a variety of methods -- in time O(dn^2) by Ford-Fulkerson, in time O(nd √n by Hopcroft-Karp, and in time O(nd) by Cole-Ost-Schirra, to name a few classic results.  Moreover, it is also easily seen that any *deterministic* algorithm must take time Ω(nd) in the worst case.  I will present a "shockingly simple"' randomized algorithm due to Goel-Kapralov-Khanna which finds such a perfect matching in expected time O(n log n).


Event Type


Events By Interest


Events By Audience


Events By School

School of Science


Department of Mathematics
Add to my calendar

Recent Activity