 |
 |
 |
 |
 |
 |
 |
 |
l |
Idea: if an edge
is k-strong, then it is in
|
|
|
a k-connected graph
|
|
|
l |
So “safe” to
sample with probability 1/k
|
|
|
l |
Problem: if sample edges with different
|
|
|
probabilities,
E[cut value] gets messy
|
|
|
l |
Solution: if sample e with probability pe,
|
|
|
|
|
give it weight 1/pe
|
|
|
l |
Then E[cut
value]=original cut value
|
|