Concepts9
Bipartite Matching - Hopcroft-Karp
Hopcroft–Karp computes maximum matching in a bipartite graph in O(E \sqrt{V}) time, which is asymptotically faster than repeated DFS (Kuhn's algorithm).
Hungarian Algorithm
The Hungarian algorithm solves the square assignment problem (matching n workers to n jobs) in O(n^{3}) time using a clever potential (label) function on vertices.
Bipartite Matching - Kuhn's Algorithm
Kuhn’s algorithm finds a maximum matching in a bipartite graph by repeatedly searching for augmenting paths using DFS.
König's Theorem
König's Theorem states that in any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Flow - Modeling Techniques
Many classic problems can be modeled as a maximum flow problem by building the right network and capacities.
Minimum Cost Maximum Flow
Minimum Cost Maximum Flow (MCMF) finds the maximum possible flow from a source to a sink while minimizing the total cost paid per unit of flow along edges.
Min-Cut Max-Flow Theorem
The Max-Flow Min-Cut Theorem says the maximum amount you can push from source to sink equals the minimum total capacity you must cut to disconnect them.
Maximum Flow - Dinic's Algorithm
Dinic's algorithm computes maximum flow by repeatedly building a level graph with BFS and sending a blocking flow using DFS.
Maximum Flow - Ford-Fulkerson
Ford–Fulkerson finds the maximum possible flow from a source to a sink by repeatedly pushing flow along an augmenting path in the residual graph.