An analysis of a random algorithm for estimating all the matchings

Jinshan Zhang, Yan Huo, Fengshan Bai

Counting the number of all the matchings on a bipartite graph has been transformed into calculating the permanent of a matrix obtained from the extended bipartite graph by Yan Huo,…