1
$\begingroup$

To find the maximum matching on a bipartite graph, I propose the following greedy algorithm: At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours if possible. Remove the 2 matched vertices and all of it's edges from the graph and repeat till the graph is empty.

I've tried finding a counter example for this greedy algorithm, but am not able to come up with one.

Could someone provide me with a counter example? Thanks!

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Here's a counter example on codeforces. However if it's complete bipartite matching, we can use the greedy Nobel winning algorithm in Economics.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.