 |
 |
4 of 18 |  |
 |
 |
MIT
Past Work: Contraction
l
If an edge doesn’t cross min-cut, then
its endpoints can be merged.
l
Subproblem: find a contractible edge
»
[NI]
O(mn)
time
»
[KS] O(n
2
) time (parallelizes)
l
Undirected graphs only