 |
 |
7 of 18 |  |
 |
 |
MIT
Finding Trees
l
A (fractional) packing can be found by:
»
Gabow’s
tree
-augmenting algorithm
–
adds one tree in O
*
(m)
time
»
[PST] generic packing algorithm
–
"uncongests" by 1/© in O
*
(m)
time (MST)
l
Either approach takes O
*
(mc
)
time
l
If only c were small....