Doubts about Min-cost flow

Revision en1, by jpgmoreira, 2020-02-20 01:36:35

Hi, I'm studying about the minimum-cost flow problem, but I got a little confused because I found two different definitions to this problem.

1) From the definition found here, there is no source or sink nodes in the flow network. Each node has a number bi called the supply value of the node, such that if bi > 0 the node is a supply node, and if bi < 0 node is a demand node. The objective is then to find a flow association to the arcs, such that the constraints posed are respected, and the total cost of the flow is minimized.

2) From definition found here however, there is one source and one sink nodes, and no supply values to nodes as above. The objective is, from the set of all maximum flows from source to sink, find one that has the minimum total cost.

I would like to get some help also to clarify if the "Min-cost flow" and "Min-cost Max-flow" are two different problems, or if those are just two names to a same problem.

Thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English jpgmoreira 2020-02-20 01:36:35 1111 Initial revision (published)