The simultaneous consecutive ones problem

DOI10.1016/J.TCS.2008.12.039MaRDI QIDQ1019172zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The weighted consecutive ones problem for a fixed number of rows or columns.
• scientific article; zbMATH DE number 2003406
• scientific article; zbMATH DE number 3848609
• scientific article; zbMATH DE number 1696653
• scientific article; zbMATH DE number 1594515

Cites work

• A structure theorem for the consecutive 1's property
• scientific article; zbMATH DE number 1187154 (Why is no real title available?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The NP-completeness of the bandwidth minimization problem
• The weighted consecutive ones problem for a fixed number of rows or columns.

Cited in

(10)

• On consecutive numbers of the same height in the Collatz problem
• The weighted consecutive ones problem for a fixed number of rows or columns.
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• Iterated local search for consecutive block minimization
• scientific article; zbMATH DE number 3848609 (Why is no real title available?)
• scientific article; zbMATH DE number 1953198 (Why is no real title available?)
• scientific article; zbMATH DE number 2003406 (Why is no real title available?)
• \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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1019172)