Wing

Network Flow

1950s

Hungarian Algorithm

Harold Kuhn, 1955

Solves the assignment problem by finding the optimal one-to-one matching that minimizes total cost in a cost matrix.

Ford-Fulkerson (Max Flow)

L.R. Ford Jr. & D.R. Fulkerson, 1956

Computes maximum flow in a network by repeatedly finding augmenting paths and pushing flow along them.

1960s

Min-Cost Max Flow

Ford & Fulkerson / Busacker & Gowen, 1961

Send maximum flow through a network while minimizing the sum of edge costs times flow.

1970s

Edmonds-Karp (Max Flow)

Jack Edmonds & Richard Karp, 1972

An implementation of Ford-Fulkerson using BFS to always find the shortest augmenting path, guaranteeing polynomial time.