Network Flow

We can generalize the bipartite matching problem quite a bit.

A beautiful generalization is network flow:

Can be solved efficiently using a generalization of augmenting paths: O(|V||E|2).

Matching is a special case: unit capacities, flow left to right.


next up previous
Next: Linear Programming Up: GENERALIZATIONS Previous: GENERALIZATIONS