Maximum Flow Problem

From IFORS Education Resources
Jump to: navigation, search

By: Yogi Sharma


The bipartite matching problem in the one that motivated the study of maximum ows. In a bipartite graph, the node set can be partitioned into two sets, L and R, such that all edges are between nodes of L and R (and no edge is between vertices in L or R). A matching in a bipartite graph is a set of edges E0 C E such that edges in E0 don't intersect, where e and f intersect if they share a common end point. The Maximum Bipartite Matching Problem seeks to find a bipartite matching of maximum cardinality.

Link to material:

Personal tools