Balanced 0-1 Matrices I. Decomposition
Balanced 0-1 Matrices I. Decomposition
复制标题
平衡0-1矩阵一、分解
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
M. Conforti;Gérard Cornuéjols;Ajai Kapoor;Kristina Vuskovic
一个0±1的矩阵是平衡的，如果在每一行和每一列有两个非零元素的平方子矩阵中，元素的和是4的倍数。本文推广了Conforti， Cornuejols, and Rao （1999， J. Combin）得到的平衡0,1矩阵的分解。Ser的理论。B77、292 ?406)到平衡的0，±1矩阵的类。因此，我们得到了一个多项式时间算法来识别平衡的0，±1矩阵。
A 0, ±1 matrix is balanced if, in every square submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This paper extends the decomposition of balanced 0, 1 matrices obtained by Conforti, Cornuejols, and Rao (1999, J. Combin. Theory Ser. B77, 292?406) to the class of balanced 0, ±1 matrices. As a consequence, we obtain a polynomial time algorithm for recognizing balanced 0, ±1 matrices.