Tractability and approximability of maximal strip recovery
DOI10.1016/J.TCS.2012.04.034zbMATH Open1252.68349OpenAlexW2104689036MaRDI QIDQ441877FDOQ441877
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
Recommendations
Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Title not available (Why is that?)
- On recovering syntenic blocks from comparative maps
- Maximal strip recovery problem with gaps: hardness and approximation algorithms
- Exact and approximation algorithms for the complementary maximal strip recovery problem
- An improved approximation algorithm for the complementary maximal strip recovery problem
- Efficient exact and approximate algorithms for the complement of Maximal Strip Recovery
- Inapproximability of maximal strip recovery
- 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
- A retrospective on genomic preprocessing for comparative genomics
- Inapproximability of maximal strip recovery
- 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)
