Is there an algorithm which can compute all perfect matchings of a general undirected graph (assuming they exist)?

  • $\begingroup$ definitely yes. you can iterate all possible solutions over vertices and check if it is a perfect match. Are you looking for efficient one? Why you need all perfect matches? $\endgroup$ – Mohsen Ghorbani Jul 9 at 16:47
  • $\begingroup$ Is the graph finite? $\endgroup$ – Yonatan N Jul 9 at 17:35
  • $\begingroup$ Yes. I am looking for an efficient algorithm to find all perfect matchings in general finite undirected graphs, G, of size 100-300 nodes and edges because these correspond to vertex-disjoint cycle covers in a second graph, H, using Tutte's reduction method. The second graph, H, represents a molecular structures and the vertex- disjoint cycle covers correspond to cyclic patterns in the bonding, hence, all the perfect matchings would be needed as they may have physical meaning. $\endgroup$ – Ganapati Natarajan Jul 10 at 11:38
  • $\begingroup$ It is np-hard for enumerating all PMs in general graphs. you can find the algorithm here $\endgroup$ – Mohsen Ghorbani Jul 10 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.