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 条

[11] A COMBINATORIAL DECOMPOSITION-THEORY [J].

CUNNINGHAM, WH ;

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1980, 32 (03) :734-765

[12]

Fulkerson D. R., 1974, MATH PROGRAMMING STU, V1, P120

[13]

Georgakopoulos G., 1988, Journal of Complexity, V4, P1, DOI 10.1016/0885-064X(88)90006-4

[14]

GHOUILAHOURI A, 1962, CR HEBD ACAD SCI, V254, P1192

[15] DECOMPOSITION OF REGULAR MATROIDS [J].

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (03) :305-359

[16] ALPHA-BALANCED GRAPHS AND MATRICES AND GF(3)-REPRESENTABILITY OF MATROIDS [J].

TRUEMPER, K .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1982, 32 (02) :112-139

[17]

Truemper K., 1992, Matroid decomposition

[18]

TRUEMPER K, 1990, 3490 UTDCS

← 1 2 →