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