Solves
matching
Articles
GRA
Algorithm
Dinic's algorithm
Maximum flow in phases: a layered network, a blocking flow, pointers; O(V²E), and O(E√V) in unit networks.
O(V² E)
2 problems
GRA
Algorithm
Bipartite matching
The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall.
O(E √V)
2 problems
GRA
Algorithm
Hungarian algorithm
Which job for whom at the least total cost: potentials, tight pairs and augmenting paths in O(n³).
O(n³)
2 problems
Problems
Often together
classic 3 flows 2 graph 2 logistics 2 contests 2 connectivity 1 networks 1 scheduling 1 images 1 interviews 1 optimization 1 matrix 1