Week 5: String Algorithms, Approximation, Randomisation, Ethics (133)

Contraction (cont)

Randomised algorithm for graph contraction = repeated edge contraction until 2 vertices remain

contract(G):
|  Input  graph G = (V,E) with |V|≥2 vertices
|  Output cut of G
|
|  while |V|>2 do
|     randomly select e∈E
|     contract edge e in G
|  end while
|  return the only cut in G