Network Flows - II

Getting Started with Competitive Programming

(an NPTEL course)

Week 9. Network Flows - II

In this week, the focus will be on the minimum cut problem, which turns out to be equal to the maxflow. We study a couple of problems where we are required to find the minimum cut or related quantities, and revisit IPL elimination.

Class Plan & Materials

A. Prerequisites
1. MaxFlow-MinCut Duality
2. Police Chase
3. Minimum Vertex Cover
Z. Extras