Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2012:journals:jeanpaul:chaptersevensectionii [2012/04/02 11:24] – created mugabej | courses:cs211:winter2012:journals:jeanpaul:chaptersevensectionii [2012/04/02 11:25] (current) – [Analyzing the Algorithm:Max-Flow Equals Min-Cut] mugabej | ||
|---|---|---|---|
| Line 16: | Line 16: | ||
| * Given a flow f of maximum value, an s-t cut can be computed of minimum capacity can be computed in O(m) time | * Given a flow f of maximum value, an s-t cut can be computed of minimum capacity can be computed in O(m) time | ||
| * In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut | * In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut | ||
| - | * If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer\\\ | + | * If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer\\ |
| \\ | \\ | ||
| I give this section an 8/10 | I give this section an 8/10 | ||
