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