| Sampling |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Use G(r/c) with e=1/8 |
|||||||||||
| » | pack O*(r) trees
in O*(m)
time |
|||||||||||
| » | original
min-cut has (1+e)r edges in G(r / c) |
|||||||||||
| » | some tree 2-crosses it in G(r / c) |
|||||||||||
| » | …and thus 2-crosses it in G |
|||||||||||
| l | Analyze
O*(r) trees in G |
|||||||||||
| » | time O*(m)
per tree |
|||||||||||
| l | Monte
Carlo |
|||||||||||
