Circulation problem: Difference between revisions

Revision as of 09:13, 5 July 2012

Revision as of 19:20, 16 July 2012

Line 48:

* [[Minimum cost multi-commodity flow problem]] - As above, but minimise the cost.

* [[Minimum cost flow problem]] - As above, with 1 commodity.

* [[Maximum flow problem]] - Set all costs to 0, and add an edge from the sink <math>t</math> to the source <math>s</math> with <math>l(t,s)=0</math>, <math>cu(t,s)=</math>∞ and <math>ac(t,s)=-1</math>.

* [[Minimum cost maximum flow problem]] - First find the maximum flow amount <math>m</math>. Then solve with <math>l(t,s)=c(t,s)=m</math> and <math>a(t,s)=0</math>.

* [[Shortest path problem|Single-source shortest path]] - Let <math>l(u,v)=0</math> and <math>c(u,v)=1</math> for all edges in the graph, and add an edge <math>(t,s)</math> with <math>l(t,s)=c(t,s)=1</math> and <math>a(t,s)=0</math>.