|
Problem Old
Time New Time |
|
|
|
|
|
|
|
| Approx. s-t min-cut
O*(mn)
O*(n2
/ e2) |
||||||
| Approx. s-t max-flow
O*(m3/2
) O*(mn1/2 /
e) |
||||||
| Flow of value v
O*(mv) |
||||||
| O*(n11/9v) |
||||||
| Approx.
bisection O*(m2) O*(n2
/ e2) |
||||||
| m Þ n
/e2
in weighted, undirected graphs |
||||||