| Analyze Trees |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Recall: [G] packs c
(directed)-edge |
|||||||||||
| disjoint spanning
trees |
||||||||||||
| l | Corollary: in such a packing, some tree |
|||||||||||
| crosses min-cut
only twice |
||||||||||||
| l | To find min-cut: |
|||||||||||
| » | find tree packing |
|||||||||||
| » | find smallest cut
with 2 tree edges crossing |
|||||||||||
| l | Problem:
packing takes O*(mc)
time |
|||||||||||