MIT
23
Recursive Algorithm
l
Algorithm RCA (
G
,
n
)
l
{
G
has
n
vertices}
l
repeat
twice
l
randomly contract
G
to
n
/
2
½
vertices
l
RCA(
G
,
n
/2
1/2
)
l
(50-50 chance of avoiding min-cut)
