Menger-decomposition of a graph and its application to the structural analysis of a large-scale system of equations (Q1100219)

The M-decomposition is defined for a graph, representing a large-scale system of nonlinear equations, with specified entrance and exit vertices, in terms of the Menger-type linkings from the entrance to the exit. Some properties of the M-decomposition are shown; in particular it is noted that the M-decomposition agrees with the Dulmage-Mendelsohn decomposition of the associated bipartite graph. The M-decomposition is useful for the structural analysis of systems of equations - it leads to the finest block-triangularization and the resulting subproblems are structurally solvable.