Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2012:journals:jeanpaul:chaptersevensectionvii [2012/04/02 12:22] – created mugabej | courses:cs211:winter2012:journals:jeanpaul:chaptersevensectionvii [2012/04/02 16:56] (current) – [Designing And Analyzing an Algorithm for Circulations] mugabej | ||
|---|---|---|---|
| Line 13: | Line 13: | ||
| * For each v ∈ V: f< | * For each v ∈ V: f< | ||
| * Feasibility Problem: We want to know if there exists a circulation that satisfies the just-mentioned conditions | * Feasibility Problem: We want to know if there exists a circulation that satisfies the just-mentioned conditions | ||
| - | * If there exists a feasible circulation with demands {d(v)}, then ∑< | + | * If there exists a feasible circulation with demands {d(v)}, then ∑< |
| + | \\ | ||
| + | ===== Designing And Analyzing an Algorithm for Circulations ===== | ||
| + | \\ | ||
| + | * The problem of finding feasible circulation can be reduced to the problem of finding a maximum s-t flow in a different network. | ||
| + | * Add new source s and sink t | ||
| + | * For each v with d(v) < 0, add edge (s, v) with capacity -d(v) | ||
| + | * For each v with d(v) > 0, add edge (v, t) with capacity d(v) | ||
| + | * ∑< | ||
| + | * Claim: G has circulation iff G' has max flow of value D | ||
| + | * Given (V, E, c, d), there //does not exist// a circulation iff there exists a node partition (A, B) such that: | ||
| + | * Σ< | ||
| + | \\ | ||
| + | ===== The Problem: Circulations with Demands And Lower Bounds ===== | ||
| + | \\ | ||
| + | * In many problems, not only do we want to satisfy demands at various nodes, but we also want to enforce the flow to make use of certain edges. | ||
| + | * That's why we need to place //lower bounds// on edges as well as the //upper bounds// restricted by the capacities | ||
| + | * Feasible circulation | ||
| + | * Directed graph G = (V, E) | ||
| + | * Edge capacities c(e) and lower bounds l(e)(Force flow to use certain edges), e ∈ E | ||
| + | * Node supply and demands d(v), v ∈ V | ||
| + | * A circulation is a function that satisfies: | ||
| + | * For each e ∈ E: 0 ≤ l(e) ≤ f(e) ≤ c(e) (capacity) | ||
| + | * For each v ∈ V: f< | ||
| + | * Goal: Decide whether or not there exists a feasible circulation(the circulation that satisfies the above conditions)\\ | ||
| + | \\ | ||
| + | ===== Designing And Analyzing an Algorithm with Lower Bounds ==== | ||
| + | \\ | ||
| + | * Strategy: Reduce the problem to the one of finding a circulation with demands but no lower bounds, which can in turn be reduced to the Maximum-Flow Problem. | ||
| + | * How to proceed?: | ||
| + | * On each edge, we need to send at least l(e) units of flow. | ||
| + | * Update demands of both endpoints\\ | ||
| + | \\ | ||
| + | I give this section a 7/10. | ||
| + | |||
