perfect_matching_counting (543B)
1 # Counting perfect matchings 2 3 - On [planar_graphs], we can exactly count [perfect_matchings] via the [FKT_algorithm] 4 - [Approximate_counting]: 5 - There is a [FPRAS] to count [perfect_matchings] on [bipartite_graphs] via [markov_chain_monte_carlo]. 6 - connection to [permanent]? 7 - For [perfect_matchings] and general [graphs], the existence of an approximation algorithm is an [open_problem]. 8 9 See also: [matching_counting] 10 11 Up: [counting_problem] of [perfect_matching] 12 13 Aliases: counting perfect matchings, counting of perfect matchings