MIT
48
Approximate Tree Packing
lBreak edges into c /r random
groups
lEach looks like a
sample at rate r / c
»O*( rm / c) edges
»each
has min expected cut r
»so
theorem says min-cut (1 – e) r
lSo each has a
packing of size (1 – e) r
l[Gabow] finds in
time O*(r2m/c) per group
»so
overall time is (c
/r ) × O*(r2m/c) = O*(rm)