Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 05:18] – [Section 3: Choosing Good Augmenting Paths] shangw | courses:cs211:winter2011:journals:wendy:chapter7 [2011/04/04 05:39] (current) – [Section 3: Choosing Good Augmenting Paths] shangw | ||
|---|---|---|---|
| Line 39: | Line 39: | ||
| The idea is that for each iteration, we hope to gain a flow value as big as possible. The way to do so is that we maintain a scaling parameter and look for paths that have bottleneck capacity of at least that value (by not considering edges whose remaining capacity is lower than that value); if there is no such path, then we reduce the scaling parameter by half. So basically if the parameter is shrunk to 1, then it is the same as increment of 1 in the original method (Gf(delta)=Gf). | The idea is that for each iteration, we hope to gain a flow value as big as possible. The way to do so is that we maintain a scaling parameter and look for paths that have bottleneck capacity of at least that value (by not considering edges whose remaining capacity is lower than that value); if there is no such path, then we reduce the scaling parameter by half. So basically if the parameter is shrunk to 1, then it is the same as increment of 1 in the original method (Gf(delta)=Gf). | ||
| The number of iterations of the outer while loop in the algorithm provided in the book is easy to be seen as O(log_2 C). | The number of iterations of the outer while loop in the algorithm provided in the book is easy to be seen as O(log_2 C). | ||
| + | It is not hard to see that during the delta-scaling phase, the increment of the augmentation would promote the flow at least O(delta). Consequently, | ||
| + | |||
| + | Readability is 7. | ||
