0
$\begingroup$

Can anybody describe what the minimum flow in a graph network is please? I am not referring to the Minimum Cost Flow Problem here.

The minimum flow I believe is the opposite to the max flow of a network. The max flow seems intuitive in that you are trying to find the max flow through a network and you could use the min-cut approach.

But I cannot understand the minimum flow of a network. This is a paper that discuss the concept. I thought that the min flow of a network is 0 but obvious that has no value.

Minflow 1 Minflow 2

Paper

$\endgroup$
0
$\begingroup$

For a minimum flow problem, we take a network where each edge $e$ has an interval $[l_e, u_e]$ associated with it; the requirement for a feasible flow is (in addition to the flow condition) that the flow along $e$ must fall into this interval.

This is is a generalization of the networks usually used in the maximum flow problems, where the interval for an edge $e$ with capacity $c_e$ is $[0, c_e]$. However, if $l_e > 0$ for some edges, then the $0$ flow is not feasible, and so the minimum flow is not trivial to find.

Typically, minimum flow algorithms work in two steps: first, we find some feasible flow, and then we try to improve it to be minimum. The first step can be done by a reduction to the maximum flow problem (it's outlined here starting from p. 9, for example). The second step uses specialized algorithms.

$\endgroup$
  • $\begingroup$ thank you for your help. I've updated my original question and I would be very grateful if you could perhaps comment further on it. The paper proposes a method to schedule a DAG considering memory constraints. The maximum topological cut, finds the peak memory of the DAG. However, in order to find the maximum topological cut the author suggests finding the minflow first. I don't quite understand the advantage of this though and I'd appreciate any help. $\endgroup$ – cherry aldi Jan 7 at 16:39

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.