A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices

DOI10.1137/S0895479893255901zbMath0829.15008MaRDI QIDQ4842560

Satoru Iwata, Kazuo Murota

Publication date: 24 January 1996

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

zbMATH Keywords

matrix decompositionDulmage-Mendelsohn decompositionHall-Ore theoremKönig- Egerváry theorem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Canonical forms, reductions, classification (15A21)

Related Items (11)

A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices ⋮ A cost-scaling algorithm for computing the degree of determinants ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices ⋮ On the complexity of submodular function minimisation on diamonds ⋮ Computing DM-decomposition of a partitioned matrix with rank-1 blocks ⋮ Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces ⋮ A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices ⋮ Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings ⋮ Signed ring families and signed posets ⋮ A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices

This page was built for publication: A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices