A new characterization of matrices with the consecutive ones property |
| |
Authors: | NS Narayanaswamy R Subashini |
| |
Institution: | a Indian Institute of Technology Madras, Chennai, India b National Institute of Technology, Calicut, India |
| |
Abstract: | We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment. |
| |
Keywords: | Interval graphs 0-1 matrices Consecutive ones property |
本文献已被 ScienceDirect 等数据库收录! |
|