A binary matrix has the Consecutive Ones Property (C1P) if there exists a permutation of its columns (i.e. a sequence of column swappings) such that in the resulting matrix the 1s are consecutive in every row. A Minimal Conflicting Set (MCS) of rows is a set of rows that does not have the C1P, but such that any proper subset of has the C1P. In [5], Chauve et al. gave a O(Δ^2 m max (4,Δ + 1) (n + m + e)) time algorithm to decide if a row of a m ×n binary matrix with at most Δ 1s per row belongs to at least one MCS of rows. Answering a question raised in [2], [5] and [25], we present the first polynomial-time algorithm to decide if a row of a m ×n binary matrix belongs to at least one MCS of rows.
A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row.
RIZZI, ROMEO;
2011-01-01
Abstract
A binary matrix has the Consecutive Ones Property (C1P) if there exists a permutation of its columns (i.e. a sequence of column swappings) such that in the resulting matrix the 1s are consecutive in every row. A Minimal Conflicting Set (MCS) of rows is a set of rows that does not have the C1P, but such that any proper subset of has the C1P. In [5], Chauve et al. gave a O(Δ^2 m max (4,Δ + 1) (n + m + e)) time algorithm to decide if a row of a m ×n binary matrix with at most Δ 1s per row belongs to at least one MCS of rows. Answering a question raised in [2], [5] and [25], we present the first polynomial-time algorithm to decide if a row of a m ×n binary matrix belongs to at least one MCS of rows.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
