Balanced 0,+/-1-matrices, bicoloring and total dual integrality

被引：18

作者：

Conforti, M ^{[1
]}

Cornuejols, G ^{[1
]}

机构：

[1] CARNEGIE MELLON UNIV, PITTSBURGH, PA 15213 USA

来源：

MATHEMATICAL PROGRAMMING | 1995年 / 71卷 / 03期

基金：

美国国家科学基金会;

关键词：

combinatorial optimization; integrality of polyhedra; generalized set packing; covering;

D O I：

10.1007/BF01590956

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A 0, +/-1-matrix A is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This definition was introduced by Truemper (1978) and generalizes the notion of a balanced 0, 1-matrix introduced by Berge (1970). In this paper, we extend a bicoloring theorem of Berge (1970) and total dual integrality results of Fulkerson, Hoffman and Oppenheim (1974) to balanced 0, +/-1-matrices.

引用

页码：249 / 258

页数：10

共 19 条

[1]

BERGE C, 1980, MATH PROGRAM STUD, V12, P163, DOI 10.1007/BFb0120894

[2] MINIMAX RELATIONS FOR THE PARTIAL Q-COLORINGS OF A GRAPH [J].

BERGE, C .

DISCRETE MATHEMATICS, 1989, 74 (1-2) :3-14

[3]

BERGE C, 1970, ANN NY ACAD SCI, V175, P32

[4]

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

[5]

Berge C, 1972, MATH PROGRAM, V2, P19, DOI 10.1007/BF01584535

[6]

Berge C., 1984, ANN DISCRETE MATH, V21, P3

[7]

CDAMION P, 1963, CAHIERS CTR ETUDES R, V5, P181

[8]

CONFORTI M, IN PRESS J COMBINA B

[9]

CONFORTI M, 1991, DECOMPOSITION BALA 1

[10]

CONFORTI M, IN PRESS J ASS COMPU

← 1 2 →