| Analysis |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Theorem: if
sample with probabilities |
||||||||||
| ar/ke, and a > v/(v-f), then will find |
|||||||||||
| augmenting path
w.h.p. |
|||||||||||
| l | Runtime: |
||||||||||
| » | 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) |
||||||||||
