Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2012:journals:ian:chapter7 [2012/04/04 04:01] – 7.5 sturdyi | courses:cs211:winter2012:journals:ian:chapter7 [2012/04/04 04:06] (current) – 7.7 sturdyi | ||
|---|---|---|---|
| Line 19: | Line 19: | ||
| * No insights. | * No insights. | ||
| * No complaints. | * No complaints. | ||
| + | |||
| + | ====== 7.7 Extensions ====== | ||
| + | |||
| + | * The algorithm can also handle distributed sources and sinks (each node has a supply or demand associated with it). Add a source with edges to each supply node with capacity equal to the supply of the incident node, and likewise add a sink connected to demand nodes. A circulation exists iff the maximum flow through this graph equals the sum of supplies and the sum of demands. One can further generalize to have lower bounds for nodes; before modeling the supply and demand, increase the demand of origin nodes of edges with lower bounds by that bound, and likewise decrease the demand of the destination nodes, and then solve as above for a maximum flow. | ||
| + | * No questions. | ||
| + | * No insights. | ||
| + | * No complaints. | ||
| + | |||
