1
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ translated from math notation into English I think this is saying while the set M is empty; while no more edges can be added to the graph, select an edge which does not have any vertex in common with edges in m; then make a union of m and new edge e, this new M is matching $\endgroup$ Apr 13, 2014 at 18:49
0
$\begingroup$

Here is a link describing the bipartite matching algorithm, including a worked out example.

http://www.dreamincode.net/forums/topic/304719-data-structures-graph-theory-bipartite-matching/

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .