| Generalization |
|
|
|
|
|
|
|
|
|
|
|
|
| l | If G has min-cut c, cut £ac is a-mincut |
||||||||||
| l | Lemma:
contraction algorithm finds any |
||||||||||
| given a-mincut
with probability W (n-2a) |
|||||||||||
| » | Proof: just add a factor to basic analysis |
||||||||||
| l | Corollary:
O(n2a) a-mincuts |
||||||||||
| l | Corollary:
Can find all in O*(n2a) time |
||||||||||
| » | Just change
contraction factor in RCA |
||||||||||
