 |
 |
8 of 32 |  |
 |
 |
MIT
Contraction Algorithm
l
Repeat
n-1
times:
»
find non-min-cut edge
»
contract it
l
Each contraction decrements #vertices
l
At end, 2 vertices left
»
unique cut
»
corresponds to min-cut of starting graph