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)
Contraction ·multigraph G(V,E) multigraph:allow parallel edges for an edge e,contract(e) merges the two endpoints
Contraction • multigraph G e (V, E ) • multigraph: allow parallel edges • for an edge e, contract(e) merges the two endpoints
Contraction ·multigraph G(V,E) multigraph:allow parallel edges for an edge e,contract(e) merges the two endpoints
Contraction • multigraph G(V, E ) • multigraph: allow parallel edges • for an edge e, contract(e) merges the two endpoints
Karger's min-cut Algorithm MinCut multigraph G(V,E)) while IV>2 do choose a uniform e∈E; contract(e); return remaining edges;
Karger’s min-cut Algorithm MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges;
Karger's min-cut Algorithm MinCut multigraph G(V,E)) while IV>2 do choose a uniform e∈E; contract(e); return remaining edges;
Karger’s min-cut Algorithm MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges;
Karger's min-cut Algorithm MinCut multigraph G(V,E)) while IV>2 do choose a uniform e∈E; contract(e); return remaining edges;
Karger’s min-cut Algorithm MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges;
Karger's min-cut Algorithm MinCut multigraph G(V,E)) while IV>2 do choose a uniform e∈E; contract(e); return remaining edges;
Karger’s min-cut Algorithm MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges;
Karger's min-cut Algorithm MinCut multigraph G(V,E)) while IV>2 do choose a uniform e∈E; contract(e); return remaining edges;
Karger’s min-cut Algorithm MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges;
Karger's min-cut Algorithm MinCut multigraph G(V,E)) while IV>2 do choose a uniform e∈E; contract(e); return remaining edges;
Karger’s min-cut Algorithm MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges;
Karger's min-cut Algorithm MinCut multigraph G(V,E)) while IV>2 do choose a uniform e∈E; contract(e); return remaining edges; edges returned
edges returned Karger’s min-cut Algorithm MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges;