| Construction |
|
|
|
|
|
|
|
|
|
|
|
| l | To sample, must
find edge strengths |
|||||||||
| » | can’t, but
approximation suffices |
|||||||||
| l | Sparse
certificates identify weak
edges: |
|||||||||
| » | construct in
linear time [NI] |
|||||||||
| » | contain all edges
crossing cuts £ k |
|||||||||
| » | iterate until
strong components emerge |
|||||||||
| l | Iterate
for 2i-strong edges, all i |
|||||||||
| » | tricks turn it
strongly polynomial |
|||||||||