Bipartite Matching is in NCResearch Paper
Whether a perfect matching of a bipartite graph can be found by a fast parallel algorithm has been a central open question of parallel complexity since the 1980s. Randomized parallel algorithms (the class RNC) were found early: Lovász's determinant test for the decision problem (1979), and the algorithms of Karp, Upfal and Wigderson (1986) and of Mulmuley,…