Consecutive ones property testing: cut or swap

2010/08/23 by Mathieu Raffinot, Raffinot, Mathieu
Computer Science · Engineering · #Algorithms and Data Compression #graph theory and CDMA systems #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1008.3786

Abstract

Let C be a finite set of N elements and R = R₁,R₂, ..,R_m a family of M subsets of C. The family R verifies the consecutive ones property if there exists a permutation P of C such that each R_i in R is an interval of P. There already exist several algorithms to test this property in sum_i=1^m |R_i| time, all being involved. We present a simpler algorithm, based on a new partitioning scheme.

Related

• Consecutive Ones Property and PQ-Trees for Multisets: Hardness of\n Counting Their Orderings
• Faster and Simpler Minimal Conflicting Set Identification
• Hardness Results for the Gapped Consecutive-Ones Property
• Simultaneous Consecutive Ones Submatrix and Editing Problems : Classical Complexity & Fixed-Parameter Tractable Results
• Weakly Consecutive Sequences