MIT
74
lApprox. s-t min-cut     O*(mv)       O*(nv / e2)
lApprox. s-t min-cut     O*(mn)       O*(n2 / e2)
lApprox. s-t max-flow  O*(m3/2 )     O*(mn1/2 / e)
lFlow of value v           O*(mv)        O*(nv)
l
lm Þ n /e2  in weighted, undirected graphs
        Problem          Old Time   New Time