Accession Number:

AD0274181

Title:

WIDTHS AND HEIGHTS OF (0, 1)-MATRICES

Descriptive Note:

Memorandum RM-2896-PR

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1962-03-01

Pagination or Media Count:

41.0

Abstract:

Let A be an m by n 0, 1-matrix, and suppose that E is an m by epsilon submatrix of A having the property that each row of E contains at least alpha 1s. The epsilon columns of E are said to form an alpha-set of representatives for A. Let epsilonalpha be the minimal number of columns of A that form an alpha-set of representatives. The integer epsilonalpha is called the alpha-width of A. If A has alpha-width epsilonalpha, select an m by epsilonalpha submatrix E of A having the property that the number deltaalpha of rows of E containing exactly alpha 1S is as small as possible. The integer deltaalpha is called the alpha-height of A.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE