Node Capacities, K&T; Ch.7 Ex.13. In a standard st Maximum-Flow Problem, we assu

Question

Node Capacities, K&T; Ch.7 Ex.13. In a standard st Maximum-Flow Problem, we assume edges have capacities, and there is no limit on how much flow is allowed to pass through a node. In this problem, we consider a variant of the Maximum-Flow and Min-Cut problems with node capacities Let G-(V E) be a directed graph, with source s V, sink t ? V, and nonnegative node capacities c 0 for each u ? V. Given a flow f in this graph, the flow through a node u is defined as fn (v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints: fin (v) S c for all nodes. Give a polynomial-time algorithm to find an s -t maximum flow in such a node-capacitated network. Define an s-t cut for node-capacitated networks, and show that the analogue of the Max-Flow Min-Cut Theorem holds true.

Explanation / Answer

f ? 0 While ? an augmenting path P in Gf Augment flow on P Update f: fij = ? ? ? fij + ?, if (i, j) ? P; fij ? ?, if (j, i) ? P; fij , otherwise, where ? = min(i,j)?P u f ij .

Given an s-t flow f, there exists a set P of s-t paths, a set C of cycles, and weights w : P ? C ? R+ such that (i) fij = P P ?P?C:(i,j)?P w(P), ?(i, j) ? A s.t. fij > 0, (ii) |f| = P p?P w(P), (iii) |P| + |C| ? m. Proof: Start with P = C = ?. Pick (i, j) ? A with fij > 0. If such an arc doesn’t exist, we are done. Otherwise, if i 6= s there exists a k such that fki > 0. This follows from the flow conservation and from the fact that fij > 0. Similarly, if j 6= t there exists an h such that fjh > 0. Keep repeating this until we find either an s-t path or a cycle. Call this P, and set w(P) = min(i,j)?P fij . Add P to P or C. Update the flow: fij = ? ? ? fij ? w(P), if (i, j) ? P; fij + w(P), if (j, i) ? P; fij , ow. Once we are done with this, parts (i) and (ii) follow from the construction. Also notice that 3-2 at least one more arc has fij = 0, so we can only do it at most m times. Hence (iii) holds

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.