Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:david:chapter7 [2011/04/06 03:43] – [7.1 - The Maximum-Flow Problem and the Ford-Fulkerson Algorithm] margoliesd
+++ courses:cs211:winter2011:journals:david:chapter7 [2011/04/06 04:51] (current) – margoliesd
@@ Line 8: / Line 8: @@
 The Maximum-Flow problem asks us to find the greatest value of flow possible for a network such that the capacity and conservation are not violated. We say that the maximum flow from one set A into another set B must equal the minimum capacity of all edges that divide A and B. Because a natural greedy algorithm does not work, we need to find a new solution. We define a residual graph as the same sets of nodes as in the original graph, but with each edge's capacity decreased to that of the remaining capacity and reversed edge of the flow through the original edge. We check our residual graph for an augmenting path to see if we can add flow. We can run the Ford-Fulkerson algorithm on this problem in O(m+n) time.
+Readability: 7/10
+====7.2 - Maximum Flows and Minimum Cuts in a Network====
+We need to show that the Ford-Fulkerson algorithm provides the maximum flow. We divide our graph into two sets of nodes such that the source is in set A and the sink is in set B. The capacity of a cut (A,B) is the total of all capacities on edges out of A into B. This is an upper bound on the flow, but we can find a tighter one. The upper bound on any flow is that of the capacity of every cut. The maximum value of any flow is that of the capacity of the minimum cut. We note that we assume capacities are integers. In fact, we can use real numbers.
+Readability: 6/10
+====7.3 - Choosing Good Augmenting Paths====
+The number of augmentations is bounded by the total of all edge capacities. We can reduce the number of augmentations by using a scaling parameter. We look only at augmenting flows whose bottleneck capacity is at least this scaling parameter (a power of 2). Once we have no more augmenting paths using the current scaling parameter, we divide it by 2 to look at paths with smaller bottlenecks. We can run this version in O(m<sup>2</sup>log<sub>2</sub>C) time, which is much better than the O(mC) time we found for the version that does not use a scaling parameter for large values of C. There are also algorithms that can run in polynomial time.
 Readability: 7/10