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

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

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

(9)

• 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
• On finding Tucker submatrices and Lekkerkerker-Boland subgraphs

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)