Electrical Engineering and Computer Science

Theory Seminar

Planar Graph Perfect Matching is in NC

Dawei Huang

Graduate Student
University of Michigan
Friday, October 13, 2017
10:30am - 11:30am
EECS 3725

Add to Google Calendar

About the Event

Is finding a perfect matching in NC? That is, is there an efficient deterministic parallel graph for it? This has been a long outstanding question for over three decades, ever since the discovery of the RNC matching algorithm. Finding a matching on general graph is much easier than counting the number of perfect matchings. However, on planar graph, it has been long known that counting the number of perfect matching is in NC but whether there is an NC algorithm that finds one has remained open. In this seminar, I will talk about a paper uploaded last week by Anari and Vazirani, which give a first NC algorithm for finding a perfect matching.

Additional Information

Sponsor(s): CSE

Open to: Public