I'm learning Blossom Algorithm, but I am confused why you can't simply do this greedy approach that I thought of. Does anyone have a counterexample?
While no more vertices: Choose the vertex (V) with the least number of edges Considering vertices connected to that vertex V, choose one with the least number of edges. Create this edge and don't consider these two vertices anymore. Reduce the count of edges on each vertex accordingly. Repeat
E G | /| | A-B-C-D | |/ | F H
If at the first step you choose BC, you lose, because you are left with 2 odd cycles and you cannot cover all the vertices. The optimal matching is AB CD EF GH.
2.1m questions
2.1m answers
60 comments
57.0k users