Skip to Main content Skip to Navigation
Conference papers

A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row

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 R that does not have the C1P, but such that any proper subset of R has the C1P. In [5], Chauve et al. gave a O(∆2 mmax(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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620378
Contributor : Guillaume Blin <>
Submitted on : Saturday, October 22, 2011 - 4:55:39 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Monday, January 23, 2012 - 2:20:35 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

Citation

Guillaume Blin, Romeo Rizzi, Stéphane Vialette. A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row. 6th International Computer Science Symposium in Russia (CSR'11), 2011, St Petersbourg, Russia. pp.373-384, ⟨10.1007/978-3-642-20712-9_29⟩. ⟨hal-00620378⟩

Share

Metrics

Record views

506

Files downloads

473