Graph Theory37 sections · 1633 units
Open in Course

Flow with Lower Bounds

Forcing minimum flow on edges

Some problems require minimum flow on certain edges. Edge (u,v)(u,v) must carry at least l(u,v)l(u,v) flow and at most c(u,v)c(u,v) flow. Convert the problem: subtract l(u,v)l(u,v) from the capacity and add l(u,v)l(u,v) to a demand at uu and supply at vv.

Then solve the modified max flow problem. If a feasible flow exists, you can recover it from the converted solution. This technique is advanced but comes up in problems like circulation and scheduling with constraints.