Grigoriev and Karpinski [GK87] studied the perfect matching problem for bipartite graphs with polynomially bounded permanent. They showed that for such bipartite graphs the problem of deciding the existence of a perfect matchings is in NC ², and counting and enumerating all perfect matchings is in NC ³. For general graphs with a polynomially bounded number of perfect matchings, they show both problems to be in NC ³.

In this paper we extend and improve these results. We show that for any graph that has a polynomially bounded number of perfect matchings, we can construct all perfect matchings in NC ². We extend the result to weighted graphs.