MIT
90
Application
lWhen residual flow i, seek augmenting path
in a sample of mrv/ic
edges. Time O(mrv/ic).
lSum over all i from v down to 1
lTotal O(mrv (log v)/c) since S1/i=O(log v)
lHere, e can be any constant < 1 (say ½)
lSo r=O(log n)
lOverall runtime O*(mv/c)