describe an algorithm that finds as efficiently as possible a matching of maximum cardinality in any bipartiate graph
I know that matching means that in the graph no two edges share a common vertex.
But I am not sure how you would find this algorithm.
My guess if first you too pick an verticie that is of lowest degree that way fewest other verticies touch it.
And you chose that edge.
Then you start looking for vertices that do not have the first verticie.
Best Answer
Look up http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm Hopcropt-Karp algorithm for what I believe is a currently best-known solution (in terms of running time) except in very dense graphs.