On the Gapped Consecutive-Ones Property

DOI10.1016/j.endm.2009.07.020zbMath1273.05217OpenAlexW2068463402MaRDI QIDQ2851450

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

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10281/217383

zbMATH Keywords

algorithmcomputational complexityconsecutive-ones property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On computing optimal linear diagrams ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Hardness results on the gapped consecutive-ones property problem ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results

Cites Work

• A note on the consecutive ones submatrix problem.
• 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: On the Gapped Consecutive-Ones Property