A theorem on the principal structure for independent matchings

DOI10.1016/0166-218X(94)00018-9MaRDI QIDQ1897351zbMATH OpenFDO

Authors Satoru Iwata, Kazuo Murota

Publication date 27 August 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(94)00018-9

zbMATH Keywords

independent matchinglayered mixed matricesprincipal partitionprincipal structuresubmodular functions

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial optimization (90C27)

Review text

The relationship between the principal structure for the independent matching and the principal partition for submodular functions is studied. Previously known results on bipartite matchings and layered mixed matrices are special cases of this result.

Recommendations

• Principal structure of submodular systems and Hitchcock-type independent flows
• Structural properties of matroid matchings
• A note on matchings and separability
• Gallai-Edmonds structure theorem for weighted matching polynomial
• A Gallai–Edmonds‐type structure theorem for path‐matchings

Cites work

• Combinatorial Canonical Form of Layered Mixed Matrices and Its Application to Block-Triangularization of Systems of Linear/Nonlinear Equations
• Horizontal Principal Structure of Layered Mixed Matrices: Decomposition of Discrete Systems by Design-Variable Selections
• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• scientific article; zbMATH DE number 3149610 (Why is no real title available?)
• scientific article; zbMATH DE number 3861184 (Why is no real title available?)
• scientific article; zbMATH DE number 3865299 (Why is no real title available?)
• scientific article; zbMATH DE number 510841 (Why is no real title available?)
• Matching theory
• Matroid theory and its applications in electric network theory and in statics
• Principal structure of layered mixed matrices
• Principal structures of submodular systems
• Submodular functions and optimization
• Systems analysis by graphs and matroids. Structural solvability and controllability
• Use of matroid theory in operations research, circuits and systems theory

Cited in

(4)

• Principal structure of submodular systems and Hitchcock-type independent flows
• Gallai-Edmonds structure theorem for weighted matching polynomial
• Existence of independent random matching
• Theory of principal partitions revisited

This page was built for publication: A theorem on the principal structure for independent matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1897351)