Testing balancedness and perfection of linear matrices

DOI10.1007/BF01582135zbMath0788.90062OpenAlexW2061781976MaRDI QIDQ689142

M. C. Fu

Publication date: 30 May 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01582135

zbMATH Keywords

decompositionbipartite graphspolynomial algorithmsbalanced matrixauction algorithmtesting algorithmsalgorithmic verificationlinear matrixperfect matrixset packing polytope

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (8)

Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths ⋮ Balanced matrices ⋮ Properties of balanced and perfect matrices ⋮ Structural properties and decomposition of linear balanced matrices ⋮ Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets ⋮ Decomposition of balanced matrices ⋮ A polynomial recognition algorithm for balanced matrices ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution

Cites Work

• Unnamed Item
• Unnamed Item
• The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
• An algorithm for finding clique cut-sets
• Properties of balanced and perfect matrices
• Structural properties and decomposition of linear balanced matrices
• Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets
• Articulation sets in linear perfect matrices. II: The wheel theorem and clique articulations
• On certain polytopes associated with graphs
• Odd cycles and matrices with integrality properties
• On a Class of Totally Unimodular Matrices
• Structural properties and recognition of restricted and strongly unimodular matrices
• Perfect zero–one matrices
• Balanced matrices

This page was built for publication: Testing balancedness and perfection of linear matrices