Grigoriev and Karpinski studied the perfect matching problem for bipartite graphs with polynomially bounded permanent. They showed that the problem of deciding of a perfect matching is in NC2 and counting and enumerating all perfect matchings is in NC3.
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 NC2.
We extend the result to weighted graphs.