The simultaneous consecutive ones problem

DOI10.1016/j.tcs.2008.12.039zbMath1161.90474OpenAlexW2087453355MaRDI QIDQ1019172

Marcus Oswald, Gerhard Reinelt

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.039

zbMATH Keywords

NP-completenesssimultaneous consecutive ones problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Theory of computing (68Q99)

Related Items (5)

\texttt{PQser:} a Matlab package for spectral seriation ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ Recognition and drawing of stick graphs ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results

Cites Work

• Unnamed Item
• The NP-completeness of the bandwidth minimization problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The weighted consecutive ones problem for a fixed number of rows or columns.
• A structure theorem for the consecutive 1's property

This page was built for publication: The simultaneous consecutive ones problem