| Cleanup |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Approximate
max-flow can be made |
|||||||||||
| exact by
augmenting paths |
||||||||||||
| l | Integrality
problems |
|||||||||||
| » | Augmenting paths
fast for small integer flow |
|||||||||||
| » | But breakup by
smoothing ruins integrality |
|||||||||||
| l | Surmountable |
|||||||||||
| » | Flows in dense
and sparse parts separable |
|||||||||||
| l | Result:
max-flow in O*(n11/9v) time |
|||||||||||