1
$\begingroup$

I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, which is different than the typical approach of considering as variables the flow of each edge.

So far, I thought on the following. Let $f_i$ be the flow of each $s-t$ path, then the objective would be $\max_{f_i} \sum_i f_i$, subject to every $f_i$ is less or equal that the capacity of each edge on that path, plus the flow convservation constraints on each vertex. Is this correct?

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.