Concepts4

Tree DP - Matching and Covering

Tree DP solves matching, vertex cover, and independent set on trees in linear time using small state transitions per node.

#tree dp#maximum matching#vertex cover+12

⚙️AlgorithmIntermediate

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).

#hopcroft karp#bipartite matching#augmenting path+11

⚙️AlgorithmIntermediate

Bipartite Matching - Kuhn's Algorithm

Kuhn’s algorithm finds a maximum matching in a bipartite graph by repeatedly searching for augmenting paths using DFS.

#bipartite matching#kuhn algorithm#augmenting path+12

⚙️AlgorithmIntermediate

Flow - Modeling Techniques

Many classic problems can be modeled as a maximum flow problem by building the right network and capacities.

#max flow#dinic#bipartite matching+12