Clever Geek Handbook

How to Convert Bipartite Matching to Independent Set

I read the book Algorithm Design Chapter 1, it gave a very brief description of how to convert two-part matching to an independent typing problem and I don't understand.

Does anyone know any detailed layout to describe this process? Thank!

+3


source to share


1 answer


The maximum bipartite agreement is a set of edges in a bipartite graph, where the two edges are not adjacent. The maximum independent set is the set of nodes (vertices) in the graph, two adjacent vertices.



So you can transform the bidirectional matching problem into an independent set by transforming each edge in your bipartite graph to a node, and then add a face between all the newly created nodes that share a common endpoint in the original graph. Then the maximum independent set in the new graph corresponds to the maximum bipartite agreement in the original problem.

+4


source






More articles:


All Articles