C&O Reading Group - Prashant Gokhale
Title: NC algorithm to find perfect matching in planar graphs
Speaker: | Prashant Gokhale |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract: Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution.