 |
 |
18 of 32 |  |
 |
 |
MIT
Generalize
l
A cut is a-minimum
if size < ac
l
Lemma: O
(n²
a
)
cuts are a-minimum
»
consider an a
-minimum cut X
»
run contraction algorithm till 3
a
vertices
»
pick random cut
»
Pr[ pick
X ]
(
)
a
a
a
a
2
3
3
)
4
(
2
1
2
-
=
-
W
=
÷
ø
ö
ç
è
æ
-
³
Õ
n
k
n
k