A faster algorithm for finding minimum Tucker submatrices

DOI10.1007/978-3-642-13962-8_8MaRDI QIDQ3576192zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(10)

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

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)