| Application |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Compress
graph to rn=O*(n/e2) edges |
|||||||||||
| l | Find s-t max-flow in compressed graph |
|||||||||||
| l | Gives s-t mincut in compressed |
|||||||||||
| l | So approx. s-t mincut in original |
|||||||||||
| l | Assorted
runtimes: |
|||||||||||
| » | [GT] O(mn) becomes O*(n2/e2) |
|||||||||||
| » | [FF] O(mv) becomes O(nv/e2) |
|||||||||||
| » | [GR] O(m3/2) become O(n3/2/e3) |
|||||||||||
