| Exact Algorithm |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Randomly
partition edges in two groups |
|||||||||||
| » | each
like a 1/2-sample:
e = O*(c-1/2) |
|||||||||||
| l | Recursively pack
trees in each half |
|||||||||||
| » | c/2 - O*(c1/2) trees |
|||||||||||
| l | Merge packings |
|||||||||||
| » | gives
packing of size c
- O*(c1/2) |
|||||||||||
| » | augment
to maximum packing: O*(mc1/2) |
|||||||||||
| l | T(m,c)=2T(m/2,c/2)+O*(mc1/2)
= O* (mc1/2) |
|||||||||||