WIDTHS AND HEIGHTS OF (0, 1)-MATRICES

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 1's. The epsilon columns of E* are said to form an alpha-set of representatives for A. Let epsilon(alpha) be the minimal number of columns of A that form an alpha-set of representatives. The integer epsilon(alpha) is called the alpha-width of A. If A has alpha-width epsilon(alpha), select an m by epsilon(alpha) submatrix E* of A having the property that the number delta(alpha) of rows of E* containing exactly alpha 1'S is as small as possible. The integer delta(alpha) is called the alpha-height of A.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1962
Accession Number
AD0274181

Entities

People

  • D.r. Fulkerson
  • H.j. Ryser

Organizations

  • RAND Corporation

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Communication Networks
  • Computations
  • Construction
  • Decomposition
  • Flow Network
  • Graphs
  • Intervals
  • Linear Programming
  • Mathematics
  • Networks
  • Procurement
  • Switching
  • Switching Circuits
  • United States

Fields of Study

  • Computer science

Readers

  • Canine Service Warrior Training Program for Wounded Warriors in the Veterinary Industry, Supported by Donors.
  • Graph Algorithms and Convex Optimization.