Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2012:journals:paul:home [2012/04/06 02:10] – [Chapter 7] nguyenp | courses:cs211:winter2012:journals:paul:home [2012/04/06 02:17] (current) – [Chapter 7] nguyenp | ||
|---|---|---|---|
| Line 791: | Line 791: | ||
| * MORE MAGIC : Given (V, E, c, d), there does not exist a circulation iff there exists a node partition (A, B) such that the sum of all the demands is greater than cap(A,B) | * MORE MAGIC : Given (V, E, c, d), there does not exist a circulation iff there exists a node partition (A, B) such that the sum of all the demands is greater than cap(A,B) | ||
| * These two pretty much solve the problem for us. more details are on page 382 if you get confused rereading this sometime in the future | * These two pretty much solve the problem for us. more details are on page 382 if you get confused rereading this sometime in the future | ||
| - | | + | |
| + | * Same givens as last problem | ||
| + | * except!!!! we have lower bounds on each edge | ||
| + | * algorithm on page 384 | ||
| + | * Here's how we do | ||
| + | * we set teh flow along an edge to be the lower bound and then we update the demand on both nodes attached to it. | ||
| + | * the rest is self explanatory | ||
