MIT
9
Minimum Cut
lSmallest
cut of graph
lCheapest
way to separate into 2 parts
lVarious
applications:
»network
reliability (small cuts are weakest)
»subtour
elimination constraints for TSP
»separation
oracle for network design
lNot s-t
min-cut