南京大学：《随机算法 Randomized Algorithms》课程教学资源（课件讲稿）Min-Cut

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;