Menger-decomposition of a graph and its application to the structural analysis of a large-scale system of equations
type: Item
instance of: scholarly article
title: Menger-decomposition of a graph and its application to the structural analysis of a large-scale system of equations
zbMATH Open document ID: 0639.05037
DOI: 10.1016/0166-218X(87)90008-4
author: Kazuo Murota
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 4041959
zbMATH Keywords: M-decomposition
zbMATH Keywords: large-scale system of nonlinear equations
reviewed by: Maciej M. Sysło
MaRDI profile type: Publication
cites work: Q4773298
cites work: Q5331549
cites work: Coverings of Bipartite Graphs
cites work: Q3266932
cites work: Two Algorithms for Bipartite Graphs
cites work: Network Flow and Testing Graph Connectivity
cites work: Q5514188
cites work: Principal structures of submodular systems
cites work: Network flow, transportation and scheduling. Theory and algorithms
cites work: Q3934401
cites work: Q3333053
cites work: Use of matroid theory in operations research, circuits and systems theory
cites work: Structural solvability of systems of equations —A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems—
cites work: Boolean sublattices connected with minimization problems on matroids
cites work: Structural theorems for submodular functions, polymatroids and polymatroid intersections
cites work: On the structure of all minimum cuts in a network and applications
cites work: Q4166767
cites work: On an Approach to Techniques for the Analysis of the Structure of Large Systems of Equations
description: scientific article; zbMATH DE number 4041959