Dulmage-Mendelsohn decomposition
- 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.
References
The original Dulmage-Mendelsohn paper is "Coverings of bipartite graphs", AL Dulmage & NS Mendelsohn, Canad. J. Math, 1958.
External links
A good explanation of its application to systems of nonlinear equations is available in this paper: [http://www.modelica.org/events/Conference2002/papers/p21_Bunus.pdf]
An open source implementation of the algorithm is available as a part of the sparse-matrix library [http://www.spooles.org SPOOLES] .
Wikimedia Foundation.
2010.
Look at other dictionaries:
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… … Wikipedia
Nathan Mendelsohn — Nathan Saul Mendelsohn, CM, FRSC (April 14, 1917 – July 4, 2006) was an American born mathematician who lived and worked in Canada. Mendelsohn was a researcher in several areas of discrete mathematics, including group theory and combinatorics.… … Wikipedia
List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… … Wikipedia
Bipartite graph — In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V ; that is, U and V are independent sets.… … Wikipedia
Algebraic graph theory — is a branch of mathematics in which algebraic methods are applied to problems about graphs. In one sense, algebraic graph theory studies graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, the… … Wikipedia
Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… … Wikipedia
