| Flow Algorithms |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Push-relabel
[GT]: |
||||||||||||||
| » | push “excess”
around graph till it’s gone |
||||||||||||||
| » | max-flow
in O*(mn)
(note: O* hides logs) |
||||||||||||||
| – | recent O*(m3/2)
[GR] |
||||||||||||||
| » | min-cut
in O*(mn2) --- “harder” than flow |
||||||||||||||
| l | Pipelining [HO]: |
||||||||||||||
| » | save push/relabel
data between flows |
||||||||||||||
| » | min-cut
in O*(mn) --- “as easy” as flow |
||||||||||||||
