Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:cohene:home:chapter7 [2018/04/02 03:29] – [7.5: A First Application: The Bipartite Matching Problem] cohene | courses:cs211:winter2018:journals:cohene:home:chapter7 [2018/04/02 03:44] (current) – [7.7: Extensions to the Maximum-Flow Problem] cohene | ||
|---|---|---|---|
| Line 28: | Line 28: | ||
| ===== 7.7: Extensions to the Maximum-Flow Problem===== | ===== 7.7: Extensions to the Maximum-Flow Problem===== | ||
| + | There are numerous extensions to the Maximum-Flow Problem involving search components that can be solved in polynomial time. One of these extensions is Circulations with Demands. If we have multiple sources and sinks, it becomes complicated to determine where to look to solve a maximization problem. Instead of maximizing flow values, here we would look at fixed supply values for sources and fixed demand values for sinks. We still want to send flow from the sources to the demands. We now associate each node with a demand. A circulation with demands is a function of f that satisfies capacity and demand conditions. | ||
| + | We can design an algorithm for circulation and demands to find a maximum s-t flow. However, we can only find a feasible circulation with demands in G if and only if the maximum s-t flow in G' has a value of D. We can enforce this by placing lower bounds on edges and upper bounds on edge capacities. | ||
