Blocking flow: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Input == # A directed graph <math>G=(V,A)</math>. # Source <math>s\in V</math> and target <math>t\in V</math>. # An upper boud <math>u(a)</math> for each arc <math>a\in A<...") |
(→Output) |
||
| Line 7: | Line 7: | ||
== Output == | == Output == | ||
A [[Basic flow definitions#Blocking flow| | A [[Basic flow definitions#Blocking flow|blocking flow]] <math>f</math>. | ||
== Known Algorithms == | |||
# [[Blocking flow by Dinic]] | |||
# [[Three indians' algorithm]] | |||
Revision as of 15:29, 13 October 2014
Input
- A directed graph [math]\displaystyle{ G=(V,A) }[/math].
- Source [math]\displaystyle{ s\in V }[/math] and target [math]\displaystyle{ t\in V }[/math].
- An upper boud [math]\displaystyle{ u(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math].
Output
A blocking flow [math]\displaystyle{ f }[/math].