| 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 |
|||||||||||
| l | Note E[G[pe]]
= G |
|||||||||||
| Theorem: G[r / ce] |
||||||||||||
| » | approximates all
cuts by e |
|||||||||||
| » | has O (rn) edges |
|||||||||||
