Min-Cut GV,E) Partition V into two parts: S and T minimize the cut C(S,T) ● many important applications (e.g.parallel computing) deterministic algorithm: ●max-flow min-cut C(S,T) ●best known upper ={uw∈Eu∈S and v∈T} bound:O(mn n2log n)T S Min-Cut • Partition V into two parts: S and T • minimize the cut • many important applications (e.g. parallel computing) • deterministic algorithm: • max-flow min-cut • best known upper bound: O(mn + n2log n) G(V,E) |C(S, T)| = {uv ￾ E | u ￾ S
v ￾ T} C(S, T)