structural:expansion
Maximum-cardinality matching

A fundamental problem in combinatorial optimization is finding a maximum matching. This problem has various algorithms for different classes of graphs.

In an unweighted bipartite graph, the optimization problem is to find a maximum cardinality matching. The problem is solved by the Hopcroft-Karp algorithm in time O (√ V E) time, and there are more efficient randomized algorithms, approximation algorithms, and algorithms for special classes of graphs such as bipartite planar graphs, as described in the main article.