 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
l |
If
edge has strength ce, divide into br / ce
|
|
|
|
|
edges of capacity
ce /br
|
|
|
» |
Creates
br å 1/ce = brn edges
|
|
|
|
l |
Now each edge is
only 1/br fraction of
|
|
|
any cut of its
strong component
|
|
|
l |
So sampling a 1/b fraction works
|
|
|
l |
So dividing into b groups works
|
|
|
l |
Yields (1-e) max-flow
in time
|