Differences
This shows you the differences between two versions of the page.
| |
| courses:cs211:winter2011:journals:anna:chapter_7 [2011/04/02 22:05] – created poblettsa | courses:cs211:winter2011:journals:anna:chapter_7 [2011/04/02 22:22] (current) – poblettsa |
|---|
| === 7.2 Maximum Flow and Minimum Cuts in a Network === | === 7.2 Maximum Flow and Minimum Cuts in a Network === |
| |
| | This section shows that the flow we get from the Ford-Fulkerson Algorithm is the max-flow. We can use the idea of cuts to put an upper bound on the v(f). In a cut A-B, the flow is the total amount that leaves A minus the amount that comes back into A. Furthermore, we can say that the value of every flow is upper bounded by the capacity of every cut. So, if we find a cut with a capacity c, we know there cannot be a s-t flow with a value greater than c. The Ford-Fulkerson Algorithm terminates when there are no s-t paths, which is all we need to show that v(f) is the maximum. |
| |
| | If we have a flow of maximum value, we can find the s-t cut of the minimum capacity in O(m) time. This leads us to the Max-Flow Min-Cut Theorem, which says that in every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut. The book also notes that we assume integer capacities, because out algorithm could run forever with real numbers. This section is sort of tricky because there are lots of details and it seems more in depth than a lot of the past sections. |
| | |
| | === 7.3 Choosing Good Augmenting Paths === |
| | |
| | This section is about how to choose the augmenting paths for the Ford-Fulkerson Algorithm in order to improve the upper bound. If you keep choosing paths with a low bottleneck, it will take more augmentations than necessary to get the result. Instead we want to choose paths that have fairly large bottlenecks. We will call the scaling parameter Δ, and we will look for paths with a bottleneck of at least Δ. We will also have a new residual graph with only the edges with residual capacity of Δ. (Δ will be power of 2). The algorithm is on page 353-354. |
| | |
| | The Scaling-Max-Flow Algorithm is basically the same as the Ford-Fulkerson Algorithm. The only difference is that the Δ helps us choose out paths better to reduce the running time. This algorithm will still return the maximum flow value. Using the scaling, we can reduce out running time to at most O(m^2 logC) time. When C is large, this is much better than O(mC). This section makes sense to me because it clears up a lot of questions I had at the beginning of this chapter about how to actually find the augmenting paths. |
