MIT
11
Flow Algorithms
lPush-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
lPipelining
[HO]:
»save
push/relabel data between flows
»min-cut
in O*(mn) --- “as easy” as
flow