Concepts318
Category
Matrix Rank and Linear Independence
Matrix rank is the number of pivots after Gaussian elimination and equals the dimension of both the column space and the row space.
Berlekamp-Massey Algorithm
Berlekamp–Massey (BM) finds the shortest linear recurrence that exactly fits a given sequence over a field (e.g., modulo a prime).
Gaussian Elimination over GF(2)
Gaussian elimination over GF(2) is ordinary Gaussian elimination where addition and subtraction are XOR and multiplication is AND.
Linear Recurrence
A linear recurrence defines each term as a fixed linear combination of a small, fixed number of previous terms.
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).
Block-Cut Tree
A Block-Cut Tree decomposes an undirected graph into biconnected components (blocks) and articulation points, forming a bipartite tree.
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.
General Matching - Blossom Algorithm
Edmonds' Blossom Algorithm finds a maximum matching in any undirected graph, not just bipartite ones.
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.