Question: Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex has a limit l() on how much
Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex ν has a limit l(ν) on how much flow can pass through ν. Show how to transform a flow network G = (V, E) with vertex capacities into an equivalent flow network G′ = (V′,E′) without vertex capacities, such that a maximum flow in G′ has the same value as a maximum flow in G. How many vertices and edges does G′ have?
Step by Step Solution
3.53 Rating (167 Votes )
There are 3 Steps involved in it
We will construct G by splitting each vertex of G into two vertices 1 2 joined by an edge of capacit... View full answer
Get step-by-step solutions from verified subject matter experts
