| s-t Min-Cuts |
|
|
|
|
|
|
| l | Recall: if
G has min-cut c, then in G(r/c) |
||||
| all cuts
approximate their expected |
|||||
| values to within e. |
|||||
| l | Applications: |
||||
|
|
| Min-cut in |
|
| O*(mc) time [G] |
|
|
|
| Approximate/exact
in |
|
| O*((m/c) c) =O*(m) |
|
|
|
| s-t min-cut of |
|
| value v in O*(mv) |
|
|
|
| Approximate in |
|
| O*(mv/c)
time |
|
|
|
|
| l | Trouble
if c is small and v large. |
|
