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
The original Dulmage-Mendelsohn paper is "Coverings of bipartite graphs", AL Dulmage & NS Mendelsohn, Canad. J. Math, 1958.
[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.
