Network Flows and Matchings

From IFORS Education Resources
Jump to: navigation, search

By: Avrim Blum


Overview

In these next two lectures we are going to talk about an important algorithmic problem called the Network Flow Problem. Network flow is important because it can be used to express a wide variety of different kinds of problems. So, by developing good algorithms for solving network flow, we immediately will get algorithms for solving many other problems as well. In Operations Research there are entire courses devoted to network flow and its variants. Topics in today’s lecture include:

• The definition of the network flow problem

• The basic Ford-Fulkerson algorithm

• The maxflow-mincut theorem

• The bipartite matching problem


Link to material: http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1025.pdf


Personal tools