Gallai–Edmonds decomposition
In graph theory, the Gallai–Edmonds decomposition is a partition of the vertices of a graph into subsets satisfying certain properties. It is a generalization of Dulmage–Mendelsohn decomposition from bipartite graphs to general graphs.
It was proved independently by Tibor Gallai and Jack Edmonds.
It can be found using the blossom algorithm.
An extension of the Gallai–Edmonds decomposition theorem to multi-edge matchings is given in Katarzyna Paluch's "Capacitated Rank-Maximal Matchings".
