| Approximate Tree Packing |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Break edges into c /r random groups |
||||||||||
| l | Each
looks like a sample at rate r / c |
||||||||||
| » | O*( rm / c) edges |
||||||||||
| » | each has min
expected cut r |
||||||||||
| » | so theorem says
min-cut (1 – e) r |
||||||||||
| l | So each has a
packing of size (1 – e) r |
||||||||||
| l | [Gabow]
finds in time O*(r2m/c) per group |
||||||||||
| » | so
overall time is c × O*(r2m/c) = O*(r2m) |
||||||||||