A binary matrix has the Consecutive-Ones Property (C1P) if its columns can be ordered in such a way that all 1's in each row are consecutive. We consider here a variant of the C1P where columns can appear multiple times in the ordering. Although the general problem of deciding the C1P with multiplicity is NP-complete, we present here a case of interest in comparative genomics that is tractable. © 2011 Springer-Verlag

Chauve, C., Maňuch, J., Patterson, M., Wittler, R. (2011). Tractability results for the consecutive-ones property with multiplicity. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.90-103). SPRINGER-VERLAG BERLIN [10.1007/978-3-642-21458-5_10].

Tractability results for the consecutive-ones property with multiplicity

Patterson, Murray;
2011

Abstract

A binary matrix has the Consecutive-Ones Property (C1P) if its columns can be ordered in such a way that all 1's in each row are consecutive. We consider here a variant of the C1P where columns can appear multiple times in the ordering. Although the general problem of deciding the C1P with multiplicity is NP-complete, we present here a case of interest in comparative genomics that is tractable. © 2011 Springer-Verlag
paper
Computer Science (all); Theoretical Computer Science
English
Annual Symposium on Combinatorial Pattern Matching, CPM 2011 27-29 June
2011
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-364221457-8
2011
6661
90
103
open
Chauve, C., Maňuch, J., Patterson, M., Wittler, R. (2011). Tractability results for the consecutive-ones property with multiplicity. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.90-103). SPRINGER-VERLAG BERLIN [10.1007/978-3-642-21458-5_10].
File in questo prodotto:
File Dimensione Formato  
tractability_2011.pdf

accesso aperto

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 334.48 kB
Formato Adobe PDF
334.48 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/217379
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
Social impact