 |
 |
 |
 |
 |
 |
 |
 |
l |
When residual
flow i, seek augmenting
|
|
|
path in a sample
of mrv/ic edges.
Time
|
|
|
O(mrv/ic).
|
|
|
l |
Sum over all i from v down
to 1
|
|
|
l |
Total O(mrv (log v)/c)
since S1/i=O(log v)
|
|
l |
Here, e can be any constant < 1 (say ½)
|
|
l |
So r=O(log n)
|
|
|
l |
Overall runtime O*(mv/c)
|
|
|
|