Tractability and approximability of maximal strip recovery

DOI10.1016/J.TCS.2012.04.034MaRDI QIDQ441877zbMATH OpenOpenAlexFDO

Authors Laurent Bulteau, Guillaume Fertin, Irena Rusu, Minghui Jiang

Publication date 8 August 2012

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

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

zbMATH Keywords

approximation algorithmsbioinformaticsparameterized complexitycomparative genomicssynteny blocks

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Tractability and approximability of maximal strip recovery
• Inapproximability of maximal strip recovery
• On the Tractability of Maximal Strip Recovery
• Efficient exact and approximate algorithms for the complement of Maximal Strip Recovery

Cites work

• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• An improved approximation algorithm for the complementary maximal strip recovery problem
• Efficient exact and approximate algorithms for the complement of Maximal Strip Recovery
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• Inapproximability of maximal strip recovery
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• On recovering syntenic blocks from comparative maps
• On the parameterized complexity of some optimization problems related to multiple-interval graphs

Cited in

(14)

• A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
• Tractability and approximability of maximal strip recovery
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• Inapproximability of maximal strip recovery
• A retrospective on genomic preprocessing for comparative genomics
• A 42k Kernel for the Complementary Maximal Strip Recovery Problem
• The complexity of finding common partitions of genomes with predefined block sizes
• Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems
• An improved linear kernel for complementary maximal strip recovery: simpler and smaller
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• A linear kernel for the complementary maximal strip recovery problem
• Efficient exact and approximate algorithms for the complement of Maximal Strip Recovery
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• On the Tractability of Maximal Strip Recovery

This page was built for publication: Tractability and approximability of maximal strip recovery

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