What is the Minimum Flow in a graph network (not the min cost flow problem)












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 1Minflow 2



Paper










share|cite|improve this question











$endgroup$

















    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 1Minflow 2



    Paper










    share|cite|improve this question











    $endgroup$















      0












      0








      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 1Minflow 2



      Paper










      share|cite|improve this question











      $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.



      Minflow 1Minflow 2



      Paper







      graph-theory






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 7 at 16:24







      cherry aldi

















      asked Jan 7 at 14:16









      cherry aldicherry aldi

      203




      203






















          1 Answer
          1






          active

          oldest

          votes


















          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.






          share|cite|improve this answer









          $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





          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
          });


          }
          });














          draft saved

          draft discarded


















          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









          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.






          share|cite|improve this answer









          $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


















          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.






          share|cite|improve this answer









          $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
















          0












          0








          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.






          share|cite|improve this answer









          $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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Jan 7 at 15:39









          Misha LavrovMisha Lavrov

          45.6k656107




          45.6k656107












          • $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






          $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




















          draft saved

          draft discarded




















































          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.




          draft saved


          draft discarded














          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





















































          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







          Popular posts from this blog

          android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

          SQL update select statement

          'app-layout' is not a known element: how to share Component with different Modules