A polynomial recognition algorithm for balanced matrices

DOI10.1016/j.jctb.2005.02.006zbMath1071.05019MaRDI QIDQ2565686

Giacomo Zambelli

Publication date: 28 September 2005

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.02.006

zbMATH Keywords

signed bipartite graphs

Mathematics Subject Classification ID

05B20: Combinatorial aspects of matrices (incidence, Hadamard, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C22: Signed and weighted graphs

Related Items

On minimal forbidden subgraph characterizations of balanced graphs, On minimal forbidden subgraph characterizations of balanced graphs, On some graph classes related to perfect graphs: a survey, Balanced matrices, Recognizing balanceable matrices, Clique-perfectness and balancedness of some graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Testing balancedness and perfection of linear matrices
• Decomposition of regular matroids
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Properties of balanced and perfect matrices
• Structural properties and decomposition of linear balanced matrices
• Decomposition of balanced matrices
• Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• Balanced \(0,\pm 1\) matrices. II: Recognition algorithm
• Balanced \(0,\pm 1\)-matrices, bicoloring and total dual integrality
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• Balanced matrices