Dulmage–Mendelsohn decomposition
From Wikipedia, the free encyclopedia
(Redirected from Dulmage-Mendelsohn decomposition)
In graph theory, the Dulmage–Mendelsohn decomposition is a method used to create a maximal matching on a bipartite graph.
It has been used to partition meshes in finite element analysis, and to determine specified, underspecified and overspecified equations in systems of nonlinear equations.
[edit] References
- Dulmage, A. L. & Mendelsohn, N. S. (1958). "Coverings of bipartite graphs". Canad. J. Math. 10: 517–534. The original Dulmage–Mendelsohn paper
[edit] External links
- A good explanation of its application to systems of nonlinear equations is available in this paper: [1]
- An open source implementation of the algorithm is available as a part of the sparse-matrix library: SPOOLES
