| Minimum Cut |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Smallest cut of
graph |
||||||||||
| l | Cheapest way to
separate into 2 parts |
||||||||||
| l | Various
applications: |
||||||||||
| » | network
reliability (small cuts are weakest) |
||||||||||
| » | subtour
elimination constraints for TSP |
||||||||||
| » | separation oracle
for network design |
||||||||||
| l | Not s-t min-cut |
||||||||||
