Flows

algonotes
lecturenotes
Published

June 26, 2023

Acknowledgements

The choice of notation, material, and problems is a subset of Jeff Erickson’s chapters on Max Flows and Applications of Max Flows.

This week, we will learn about:

  1. The problem of finding a maximum flow in a network,
  2. the relationship between a maximum flow and a minimum cut,
  3. a pseudo-polynomial-time algorithm for finding a maximum flow [Ford-Fulkerson],
  4. a method to decompose a flow into a combination of path and cycle flows.

We will also apply the maxflow algorithm to solve the following problems:

  1. Tuple Selection
  2. Exam Scheduling
  3. IPL Elimination

Detailed notes are coming soon (will be up by 5PM on 26 Jun).

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos