MIT
79
Application
lCompress graph to
rn=O*(n/e2)
edges
lFind s-t max-flow in compressed
graph
lGives s-t mincut in compressed
lSo approx. s-t mincut in original
lAssorted
runtimes:
»[GT] O(mn) becomes O*(n2/e2)
»[FF] O(mv) becomes O(nv/e2)
»[GR] O(m3/2) become O(n3/2/e3)