Recognizing Balanceable Matrices |
| |
Authors: | Michele Conforti Giacomo Zambelli |
| |
Institution: | (1) Dipartimento di Matematica, Universitá degli Studi di Padova, Via Belzoni 7, 35131 Padova, Italy;(2) Department of Combinatorics and Optimization, University of Waterloo, 200 University Ave, Waterloo, Ontario, Canada, N2J 3G1 |
| |
Abstract: | A 0/±1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column
in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed ±1 so that
the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/±1 matrices
and balanceable 0/1 matrices are equivalent. Conforti, Cornuéjols, Kapoor and Vušković gave an algorithm to test if a 0/±1
matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we
give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists.
Received: October 2004 |
| |
Keywords: | Balanceable Matrices Recognition Algorithm |
本文献已被 SpringerLink 等数据库收录! |
|