Hardness results on the gapped consecutive-ones property problem

DOI10.1016/j.dam.2012.03.019zbMath1252.68362OpenAlexW2004476852MaRDI 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

algorithmcomputational complexitygraph bandwidthconsecutive-ones propertyancestral genome reconstruction

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Algorithms on strings (68W32)

Related Items (2)

On computing optimal linear diagrams ⋮ 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

This page was built for publication: Hardness results on the gapped consecutive-ones property problem