Balanced 0, ± 1 matrices I.: Decomposition

被引：18

作者：

Conforti, M

Cornuéjols, G

Kapoor, A

Vuskovic, K

机构：

[1] Univ Padua, Dipartimento Matemat Pura & Applicata, I-35131 Padua, Italy

[2] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA

[3] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

[4] Univ Leeds, Sch Comp Studies, Leeds LS2 9JT, W Yorkshire, England

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2001年 / 81卷 / 02期

基金：

美国国家科学基金会;

关键词：

balanced matrix; decomposition; recognition algorithm; 2-join; 6-join; extended star cutset;

D O I：

10.1006/jctb.2000.2010

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 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 fur recognizing balanced 0, +/- matrices. (C) 2001 Academic Press.

引用

页码：243 / 274

页数：32

共 18 条

[1]

BERGE C, 1970, C MATH SOC J BOLYAI, V4, P119

[2]

Berge C., 1972, Math. Program., V2, P19

[3] CHARACTERIZATION OF TOTALLY UNIMODULAR MATRICES [J].