Accession Number:

AD0650430

Title:

INCIDENCE MATRICES WITH THE CONSECUTIVE 1'S PROPERTY

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1964-11-01

Pagination or Media Count:

12.0

Abstract:

Let A aij be an m-by-n matrix whose entries aij are all either 0 or 1. For certain applications it is of interest to know whether or not there is an m-by-m permutation matrix P such that the 1s in each column of PA occur in consecutive positions. In this note certain results having relevance to this problem are stated. Proofs of these results together with computationally effective algorithms for deciding the question are to be published elsewhere. The problem formulated above is directly related to that of determining whether a given finite, undirected graph is an interval graph. Although necessary and sufficient conditions are known for the solution of this latter problem, the approach used here is quite different from those used heretofore and seems to lead to highly efficient algorithms not only for resolving the question, but also for producing a representative set of intervals in the affirmative case.

Subject Categories:

  • Biology
  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE