Consecutive Ones Property Testing: Cut or Swap

DOI10.1007/978-3-642-21875-0_25zbMath1344.68172arXiv1008.3786OpenAlexW1547013647MaRDI QIDQ3091461

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

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

Related Items (2)

Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Obtaining matrices with the consecutive ones property by row deletions

Cites Work

• Unnamed Item
• Unnamed Item
• A note on computing set overlap classes
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• PC trees and circular-ones arrangements.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A Simple Test for the Consecutive Ones Property
• A Faster Algorithm for Finding Minimum Tucker Submatrices
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Planarity Algorithms via PQ-Trees (Extended Abstract)

This page was built for publication: Consecutive Ones Property Testing: Cut or Swap