MIT
85
Approximate Flows
lUniform
sampling led to tree algorithms
»Randomly
partition edges
»Merge
trees from each partition element
lCompression
problematic for flow
»Edge
capacities changed
»So
flow path capacities distorted
»Flow
in compressed graph doesn’t fit in original graph