Consecutive ones property testing: cut or swap

DOI10.1007/978-3-642-21875-0_25MaRDI QIDQ3091461zbMATH OpenOpenAlexFDO

Authors Mathieu Raffinot

Publication date 9 September 2011

Published in Models of Computation in Context (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.3786

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Analysis of algorithms (68W40)

Abstract: Let C be a finite set of $N elements and R = {R_1,R_2, ..,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.

Recommendations

• A Simple Test for the Consecutive Ones Property
• A certifying algorithm for the consecutive-ones property
• On testing consecutive-ones property in parallel
• scientific article; zbMATH DE number 3874671
• scientific article; zbMATH DE number 5606342

Cites work

• A certifying algorithm for the consecutive-ones property
• A faster algorithm for finding minimum Tucker submatrices
• A note on computing set overlap classes
• A Simple Test for the Consecutive Ones Property
• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• PC trees and circular-ones arrangements.
• Planarity algorithms via PQ-trees (extended abstract)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(3)

• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• Obtaining matrices with the consecutive ones property by row deletions
• scientific article; zbMATH DE number 3874671 (Why is no real title available?)

This page was built for publication: Consecutive ones property testing: cut or swap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3091461)