1
$\begingroup$

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum $st$-flow where each edge $e$ has flow capacity $f(e)=0$ or $c_{min}<f(e)<c_{max}$

A search provided this possibility: https://cstheory.stackexchange.com/questions/16664/using-max-flow-ford-fulkerson-to-find-satisfying-flow

However, I wasn't sure if this problem was exactly the same.

This is a homework question. My intuition is to modify the Ford-Fulkerson method but I'm not sure how. Any hints would be greatly appreciated.

Thanks.

$\endgroup$
  • $\begingroup$ What is your question? I suggest highlighting what you need so that others know what kind of answers you a looking for. $\endgroup$ – Joonas Ilmavirta Nov 19 '14 at 7:07
  • $\begingroup$ Replace "I'm trying to develop" with "What is" at the beginning of the first paragraph. $\endgroup$ – Fred Nov 19 '14 at 7:52
0
$\begingroup$

You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of $f(e)=0$ suggests), you can tell the algorithm to check for paths where $c_f(u,v) \ge 0$, instead of $c_f(u,v) >0$ (as the Wikipedia article pseudocode states).

$\endgroup$
0
$\begingroup$

Just finding a feasible flow will be a problem in itself. You are better off using a Min Cost Flow algorithm. Add an arc $(t,s)$, set all demands to $0$ and minimize $-x_{t\,s}$.

There are many Min Cost Flow algorithms, see this link for example.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.