Circulation problem: Difference between revisions

Revision as of 07:33, 17 May 2013

Revision as of 18:59, 5 July 2013

Line 26:

|-

| <math>\,f(v,w) = \sum_i f_i(v,w)</math> || The total flow.

|}

There is also a lower bound on each flow of commodity.

:{|

| <math>\,l_i(v,w) \leq f_i(v,w)</math>

|}

Line 46 ⟶ 52:

* Multi-commodity circulation - Solve without optimising cost.

* Simple circulation - Just use one commodity, and no cost.

* [[Multi-commodity flow problem|Multi-commodity flow]] - If <math>K_i(s_i,t_i,d_i)</math> denotes a demand of <math>d_i</math> for commodity <math>i</math> from <math>s_i</math> to <math>t_i</math>, create an edge <math>(t_i,s_i)</math> with <math>ll_i(t_i,s_i) = c(t_i,s_i) = d_i</math> for all commodities <math>i</math>. Let <math>ll_i(u,v)=0</math> for all other edges.

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

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