Minimum Cuts in Near-Linear Time

MIT

56

Sampling

lUse G(r/c) with e=1/8

»pack O*(r) trees in O*(m) time

»original min-cut has (1+e)r edges in G(r / c)

»some tree 2-crosses it in G(r / c)

»…and thus 2-crosses it in G

lAnalyze O*(r) trees in G

»time O*(m) per tree

lMonte Carlo