A faster algorithm for finding minimum Tucker submatrices

DOI10.1007/978-3-642-13962-8_8zbMATH Open1286.68512OpenAlexW2163167830MaRDI QIDQ3576192FDOQ3576192

Authors: Guillaume Blin, Romeo Rizzi, Stéphane Vialette 

Publication date: 29 July 2010

Published in: Programs, Proofs, Processes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13962-8_8

Recommendations

• A faster algorithm for finding minimum Tucker submatrices
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• On the consecutive ones property
• On testing consecutive-ones property in parallel

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cited In (8)

• A faster algorithm for finding minimum Tucker submatrices
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• Consecutive ones property testing: cut or swap
• Faster and simpler minimal conflicting set identification (extended abstract)
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• Structured preferences: a literature survey

This page was built for publication: A faster algorithm for finding minimum Tucker submatrices

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