Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 16:26, 26 November 2013

Revision as of 16:30, 26 November 2013

Line 16:

==Definition==

Given a flow network <math>G(V,E)</math> with capacity from node ''u'' to node ''v'' given as <math>c(u,v)</math>, and the flow across ''u'' and ''v'' given as <math> f(u,v) </math>, source ''s'' and sink ''t'', we want to find the maximum amount of flow you can send from ''s'' to ''t'' through the network. TwoSome typeskey ofconcepts operationsused arein performedthe on nodes, ''push''algorithm and ''relabel''. Throughout we maintainare:

:{|

| '''f(u,v)''': ||Flow from ''u'' to ''v''.

|-

| '''residual edge''': ||If available capacity <math>c(u,v) - f(u,v)>0</math> we have a residual edge <math>r(u,v)</math>.

|-

Line 31 ⟶ 29:

|}

Given that we are operating on a flow network, we will give a brief description. There are three conditions for [[flow network|flow networks]]:

:{|