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