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/02 01:58] – [7.5] odells | courses:cs211:winter2014:journals:sam:home [2014/04/02 02:18] (current) – [Readability] odells | ||
|---|---|---|---|
| Line 349: | Line 349: | ||
| The Ford-Fulkerson algorithms can be used to find a maximum matching in a bipartite graph in O(mn) time. | 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. | ||
