Differences

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

--- courses:cs211:winter2011:journals:david:chapter7 [2011/04/06 04:43] – margoliesd
+++ courses:cs211:winter2011:journals:david:chapter7 [2011/04/06 04:51] (current) – margoliesd
@@ Line 16: / Line 16: @@
 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