Maximum Flow Problem

From IFORS Education Resources
Jump to: navigation, search

By: Yogi Sharma


Motivation

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: http://www.cs.cornell.edu/courses/cs4820/2010su/handouts/max-flow-handout.pdf


Personal tools