Accession Number:

ADA278170

Title:

Balanced 0, + or - Matrices. Part 1. Decomposition,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION

Personal Author(s):

• Conforti, Michele
• Cornuejols, Gerard
• Kapuur, Ajai
• Vuskovic, Kristina

Report Date:

1994-01-22

Pagination or Media Count:

53.0

Abstract:

A 0, or - 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 to the class of balanced 0, or - matrices. As a consequence, we obtain a polynomial time algorithm for recognizing balanced 0, or - matrices.

Descriptors:

• *MATRICES(MATHEMATICS)
• INTEGER PROGRAMMING
• COMBINATORIAL ANALYSIS
• DECOMPOSITION
• DETERMINANTS(MATHEMATICS)

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE