MIT
78
Compression Theorem
Definition:
Given compression probabilities pe, compressed graph G[pe]
»includes
edge e with probability pe and
»gives
it weight 1/pe if
included
lNote
E[G[pe]] = G
Theorem: G[r / ce]
»approximates
all cuts by e
»has
O (rn) edges