| Picking an Edge |
|
|
|
|
|
|
|
|
|
|
|
| l | Must 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…. |
||||||||||
| Idea: min-cut edges are few |
