What is the Minimum Flow in a graph network (not the min cost flow problem)
$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.
Paper
graph-theory
asked Jan 7 at 14:16
cherry aldicherry aldi
203
$endgroup$
add a comment |
$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.
Paper
graph-theory
asked Jan 7 at 14:16
cherry aldicherry aldi
203
$endgroup$
add a comment |
$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.
Paper
graph-theory
asked Jan 7 at 14:16
cherry aldicherry aldi
203
$endgroup$
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.
Paper
graph-theory
graph-theory
asked Jan 7 at 14:16
cherry aldicherry aldi
203
asked Jan 7 at 14:16
cherry aldicherry aldi
203
edited Jan 7 at 16:24
cherry aldi
asked Jan 7 at 14:16
cherry aldicherry aldi
203
asked Jan 7 at 14:16
cherry aldicherry aldi
203
asked Jan 7 at 14:16
cherry aldicherry aldi
203
203
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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.
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
$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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065053%2fwhat-is-the-minimum-flow-in-a-graph-network-not-the-min-cost-flow-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
$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
add a comment |
$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.
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
$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
add a comment |
$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.
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
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.
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 7 at 15:39
Misha LavrovMisha Lavrov
46.3k656107
46.3k656107
$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
add a comment |
$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
$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
$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
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065053%2fwhat-is-the-minimum-flow-in-a-graph-network-not-the-min-cost-flow-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
