|
Problem Old Time New Time |
|
|
|
|
|
|
| Approx. s-t min-cut
O*(mv)
O*(nv
/ e2) |
|||||
| 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*(nv) |
|||||
| m Þ n
/e2
in weighted, undirected graphs |
|||||
