notking's blog

Maximum flow problem
By notking, history, 7 years ago, In English

How can I solve the maximum flow problem when the capacity is not on the edge but only on the vertices? There are no multiple edges. Can I remove capacity from vertices and for each edge put its capacity equal to the minimum of capacities of 2 vertices it connects and then apply the maximum flow algorithm? Will this work?

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

Comments Comments (3)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Put Infinite capacity on edges. Then, for each vertice v, add a vertice v' and an edge from v to v' with the capacity of v.

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

    For each vertex, we make an auxiliary vertex and connect it to the main vertex with the capacity of the main vertex. Now, when we will run the maximum flow, the answer would be infinite no?

    Also, what's wrong with my approach?

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

      Maybe you understood it wrong: you make v', connect it to v with capacity c[v] (edge is directed from v to v'), and then every edge that was ended in v still ends in v, but edge which started from v now starts from v'. That way you can guarantee that through v goes not more than c[v] of flow.

      And, no, ofcourse answer will be less than infinity for the obvious reasons.

      P.S. Maybe your approach is correct, but the main way of solving such problems is to try to build equivalent graph so the max flow will be the same for it, and you are trying something a little different.

      → Reply