Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 19:39] – [7.3 Choosing Good Augmenting Paths] zhongc | courses:cs211:winter2011:journals:chen:chapter_7 [2011/04/06 20:59] (current) – [7.3 Choosing Good Augmenting Paths] zhongc | ||
|---|---|---|---|
| Line 99: | Line 99: | ||
| - | analysis of the runningtime: | + | analysis of the running time: |
| The number of iterations o[ the outer While loop is at most 1 +[log2 C]. | The number of iterations o[ the outer While loop is at most 1 +[log2 C]. | ||
| we are using paths that augment the flow by a great amount, and so there should be relatively few augmentations. | we are using paths that augment the flow by a great amount, and so there should be relatively few augmentations. | ||
| + | Let f be the [low at the end of the A-scaling phase. There is an s-t | ||
| + | cut (A, B) in G for which c(A, B) < v(f) + mA, where m is the number of edges | ||
| + | in the graph G. Consequently, | ||
| + | most v(f) + m A. | ||
| + | |||
| + | Proof on P380. | ||
| + | |||
| + | Interesting/ | ||
