کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420446 | 683939 | 2009 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A new characterization of matrices with the consecutive ones property A new characterization of matrices with the consecutive ones property](/preview/png/420446.png)
We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set SS of cardinality nn, and an assignment of intervals of the discrete set {1,…,n}{1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n}f:S→{1,…,n} such that for each element of F, its image under ff 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.
Journal: Discrete Applied Mathematics - Volume 157, Issue 18, 28 November 2009, Pages 3721–3727