INCIDENCE MATRICES WITH THE CONSECUTIVE 1'S PROPERTY
RAND CORP SANTA MONICA CA
Pagination or Media Count:
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.
- Theoretical Mathematics