Maximum bipartite graph (1,n) "matching"

Posted by Imre Kelényi on Stack Overflow See other posts from Stack Overflow or by Imre Kelényi
Published on 2009-10-05T11:13:00Z Indexed on 2010/04/03 13:33 UTC
Read the original article Hit count: 445

Filed under:
|
|

I have a bipartite graph. I am looking for a maximum (1,n) "matching", which means that each vertex from partitation A has n associated vertices from partition B.

The following figure shows a maximum (1,3) matching in a graph. Edges selected for the matching are red and unselected edges are black.

See figure

This differs from the standard bipartite matching problem where each vertex is associate with only one other vertex, which could be called (1,1) matching with this notation.

If the matching cardinality (n) is not enforced but is an upper bound (vertices from A can have 0 < x <= n associated vertices from B), then the maximum matching can be found easily by transforming the graph to a flow network and finding the max flow. However, this does not guarantee that the maximum number of vertices from A will have n associated pairs from B.

© Stack Overflow or respective owner

Related posts about graphs

Related posts about matching