| A Simple Application |
|
|
|
|
|
|
|
|
|
|
|
|
| l | [Gabow]
packs trees in O*(mc)
time |
||||||||||
| l | Build G(r / c) |
||||||||||
| » | minimum expected
cut r |
||||||||||
| » | by theorem,
min-cut probably near r |
||||||||||
| » | find
min-cut in time O*(rm) using [Gabow] |
||||||||||
| » | corresponds to
near-min-cut in G |
||||||||||
| l | Result:
(1+e) times min-cut in O*(rm) time |
||||||||||