Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:donohuem:chapter7 [2018/04/03 02:35] – donohuem | courses:cs211:winter2018:journals:donohuem:chapter7 [2018/04/03 03:13] (current) – [7.7 More on Maximum-Flow] donohuem | ||
|---|---|---|---|
| Line 24: | Line 24: | ||
| ===== 7.5 Bipartite Matching ===== | ===== 7.5 Bipartite Matching ===== | ||
| + | In this section, we revisit the Bipartite Matching Problem where we wish to find the largest bipartite matching in a graph G. The algorithm that achieves this builds off of the concept of flow networks. The algorithm takes an undirected bipartite graph and constructs a directed flow network from it. Interestingly enough, the size of the maximum matching in G is equal to the maximum flow in the corresponding flow network graph of G. The algorithm is more expensive, however, running in O(mn) time. Overall the readability of this section is 7/10. | ||
| + | |||
| + | |||
| + | |||
| + | ===== 7.7 More on Maximum-Flow ===== | ||
| + | The Maximum-Flow problem can be extended | ||
| + | |||
| | | ||
