Discover published sets by community

A matching that contains the largest possible number of edges. No additional edges can be added without violating the matching property. It's crucial for problems aiming to maximize pairings, such as in job assignments.

A graph that can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. It is important in modeling relationships between two different classes of objects.

A condition that determines if a bipartite graph has a matching that covers one set: for every subset of one part, the neighborhood of this subset is at least as large as the subset itself. It's vital for deciding if a perfect matching is possible.

A combinatorial optimization algorithm that solves the assignment problem in polynomial time by finding a maximum matching in a weighted bipartite graph. It is significant in operations research and economics for optimal assignment.

In any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover. This theorem is a cornerstone in combinatorial optimization as it establishes the min-max relation between matchings and covers.

A path that starts and ends at unmatched vertices and alternates between edges not in the matching and edges in the matching. Augmenting paths are key in algorithms for finding maximum matchings, since they can increase the size of the current matching.