Search code examples
algorithmgraphgraph-theorybipartite

Maximum Cardinality in Bipartite Graph


Is the maximum cardinality in a bipartite graph same as the maximum flow in that graph with two dummy nodes one as source other as sink.

Source is connected to one set of bipartite graph and the other set is connected to the sink.


Solution

  • If you mean "maximum cardinality matching" then yes, you can find it using maximal flow algorithms. Check "algorithms" section here.