Recently i've been dealing with a problem that led me to the following questions:
- Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph?
- Is there a good algorithm for finding all maximum/perfect matchings in a general graph?
- Are these two problems equivalent in their complexity?
I've stumbled upon the following references:
- Algorithms for Enumerating All Perfect Maximum and Maximal Matchings In Bipartite Graphs- Suggesting an algorithm for enumerating all maximum matchings in a bipartite graph.
- Finding All the Perfect Matchings in Bipartite Graphs- Suggesting an algorithm for finding all perfect matchings in bipartite graphs
Both algorithms' complexity depend on the number of perfect matchings in the graph (meaning exponential running time in the worst case).
Moreover, both articles deal with bipartite graphs, I couldn't find similar articles dealing with the same problem in general graphs.
I'd appreciate information and references about the above problems.