Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:sam:home [2014/04/01 20:47] – [7.2] odells | courses:cs211:winter2014:journals:sam:home [2014/04/02 02:18] (current) – [Readability] odells | ||
|---|---|---|---|
| Line 343: | Line 343: | ||
| ====7.5==== | ====7.5==== | ||
| + | The Bipartite Matching Problem | ||
| + | A matching in a graph G is a subset of the edges M in E such that each node appears in at most one edge in M. The Bipartite Matching problem is that of finding a matching in G of largest possible size. | ||
| + | |||
| + | The Ford-Fulkerson algorithms can be used to find a maximum matching in a bipartite graph in O(mn) time. | ||
| ====7.7==== | ====7.7==== | ||
| + | Much of the power of the Maximum-Flow Problem lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph. | ||
| + | Before, we had just one sink and one source. Now, we will have multiple! Now, instead of maximizing flow value, we will have sources that have a fixed supply and sinks that have a fixed demand, and our goal is to ship flow from nodes with available supply to those with given demands. | ||
| ====Readability==== | ====Readability==== | ||
| + | 4/10. This section is incredibly dense and hard to make sense of. I don't think the book does a great job of explaining overly technical aspects. | ||
