Hardness results on the gapped consecutive-ones property problem

DOI10.1016/j.dam.2012.03.019zbMath1252.68362MaRDI QIDQ1759853

Cedric Chauve, Murray Patterson, Ján Maňuch

Publication date: 22 November 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.03.019

zbMATH Keywords

algorithm; computational complexity; graph bandwidth; consecutive-ones property; ancestral genome reconstruction

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

68W32: Algorithms on strings

Related Items

Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results

Cites Work

• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A note on the consecutive ones submatrix problem.
• Incidence matrices and interval graphs
• A structure theorem for the consecutive 1's property
• On the Gapped Consecutive-Ones Property
• A Simple Test for the Consecutive Ones Property
• Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• A note on the NP-hardness of the consecutive block minimization problem
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems