Inapproximability of maximal strip recovery
DOI10.1016/J.TCS.2011.04.021zbMATH Open1217.92041OpenAlexW2029567123MaRDI QIDQ551208FDOQ551208
Authors: Minghui Jiang 
Publication date: 14 July 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.021
Recommendations
Complexity and performance of numerical algorithms (65Y20) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Complexity of approximating bounded variants of optimization problems
- Non-approximability results for optimization problems on bounded degree instances
- On the hardness of approximating minimum vertex cover
- On the complexity of approximating \(k\)-set packing
- Scheduling Split Intervals
- The linear arboricity of graphs
- Title not available (Why is that?)
- Covering and packing in graphs IV: Linear arboricity
- On recovering syntenic blocks from comparative maps
- Maximal strip recovery problem with gaps: hardness and approximation algorithms
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- On the complexity of unsigned translocation distance
- Non-approximability of weighted multiple sequence alignment for arbitrary metrics
- Hardness of approximation for non-overlapping local alignments.
- Tractability and approximability of maximal strip recovery
- On the Tractability of Maximal Strip Recovery
- Paired approximation problems and incompatible inapproximabilities
- Automata, Languages and Programming
Cited In (13)
- A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
- Tractability and approximability of maximal strip recovery
- An improved approximation algorithm for the complementary maximal strip recovery problem
- Tractability and approximability of maximal strip recovery
- A 42k Kernel for the Complementary Maximal Strip Recovery Problem
- On recovering syntenic blocks from comparative maps
- The complexity of finding common partitions of genomes with predefined block sizes
- An improved approximation algorithm for the complementary maximal strip recovery problem
- On Recovering Syntenic Blocks from Comparative Maps
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Maximal strip recovery problem with gaps: hardness and approximation algorithms
- Maximal strip recovery problem with gaps: hardness and approximation algorithms
- Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
This page was built for publication: Inapproximability of maximal strip recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551208)
