MIT
15
Picking an Edge
lMust contract non-min-cut edges
l[NI]: O(m) time algorithm to pick edge
»n contractions: O(mn) time for min-cut
»slightly faster than flows
»
»If only could find edge faster….
l
l
 Idea: min-cut edges are few