CODEWITHSUNDEEP
graphgraph-theorymatching
m.taheri
m.taheri

Reputation: 329

Algorithm to indicate existence of a perfect matching in a graph

I am trying to design an algorithm that indicates whethere a graph has a perfect matching or not. Is there any known or unknown algorithm to do that?

Thank you in advance.

Upvotes: 0

Views: 1943

Answers (1)

Hernán Tellechea
Hernán Tellechea

Reputation: 101

Well, you can try finding the maximum matching using the Blossom algorithm and then verify if your maximum matching is a perfect matching by checking if your maximum matching is "touching" all the elements in your set of vertices.

http://en.wikipedia.org/wiki/Blossom_algorithm

Upvotes: 3

Related Questions