metal_knight's blog

Flow
By metal_knight, 10 years ago, In English

How can I find the minimum cost max-flow in a graph where the capacity of an edge have a lower and upper bound (UPD: Edge have a capacity within a range [l,r])?

UPD: FLOW (not capacity) of an edge have a lower and upper bound

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean by lower and upper bound? If you mean that the capacity of the edge must always be within a range [l,r], then just set its capacity to r-l and do a normal flow algorithm.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes the capacity of an edge is within a range [l,r]. But your idea is not right. See this graph,

    1-->2(l=5,r=10,cost=2)

    2-->3(l=9,r=14,cost=2)

    Where source is 1 and sink is 3.

    Here, the maximum flow is 10 and the cost is 20. But according to your idea the maximum flow is 5 and the cost is 10. Correct me if I'm wrong.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      if I remember correctly the lower-bound max flow can be translated into a max-flow without lower-bounds but I'm not sure if it can be applied to costed max flow

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If the CAPACITY of the edges has to be in the ranges [5,10] and [9,14], then the answer is 5. You send 5 units of flow through the path, the capacity of the first edge decreases to 5 and the capacity of the second edge decreases to 9. No further flow can be sent.

      If, on the other hand, the FLOW that goes through the edges has to be in the ranges [5,10] and [9,14], then that's a completely different problem and the solution I suggested wouldn't work. If that's what you're actually asking, you should rephrase your post.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It was my fault. Sorry for the inconvenience. updated the post. Thanks for pointing out my mistake.

        → Reply