MIT
94
Analysis
lTheorem:
if sample with probabilities ar/ke, and a > v/(v-f), then will find augmenting
path w.h.p.
lRuntime:
» a always within a factor of 2 of “right” v/(v-f)
»As
in compression, edge count O(a r n)
»So
runtime O(r n Siv/i)=O*(nv)