Dulmage-Mendelsohn decomposition

From Wikipedia, the free encyclopedia

You have new messages (last change).

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] Reference

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.

Retrieved from "http://en.wikipedia.org../../../d/u/l/Dulmage-Mendelsohn_decomposition_95b5.html"