Dulmage–Mendelsohn decomposition
Bipartite graph partition with special property / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Dulmage–Mendelsohn decomposition?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958.[1] A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.