Inapproximability of maximal strip recovery
From MaRDI portal
Publication:551208
DOI10.1016/j.tcs.2011.04.021zbMath1217.92041OpenAlexW2029567123MaRDI QIDQ551208
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
Biochemistry, molecular biology (92C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Complexity and performance of numerical algorithms (65Y20)
Related Items
Recognizing \(d\)-interval graphs and \(d\)-track interval graphs, The complexity of finding common partitions of genomes with predefined block sizes, Maximal strip recovery problem with gaps: hardness and approximation algorithms, Tractability and approximability of maximal strip recovery, A 42k Kernel for the Complementary Maximal Strip Recovery Problem, An improved linear kernel for complementary maximal strip recovery: simpler and smaller
Cites Work
- Unnamed Item
- Unnamed Item
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- On the hardness of approximating minimum vertex cover
- On the complexity of unsigned translocation distance
- On recovering syntenic blocks from comparative maps
- Non-approximability of weighted multiple sequence alignment for arbitrary metrics
- The linear arboricity of graphs
- Optimization, approximation, and complexity classes
- Hardness of approximation for non-overlapping local alignments.
- Some APX-completeness results for cubic graphs
- Complexity of approximating bounded variants of optimization problems
- On the complexity of approximating \(k\)-set packing
- Tractability and Approximability of Maximal Strip Recovery
- Inapproximability of Maximal Strip Recovery: II
- On the Tractability of Maximal Strip Recovery
- Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms
- Covering and packing in graphs IV: Linear arboricity
- Non-approximability results for optimization problems on bounded degree instances
- Automata, Languages and Programming
- Scheduling Split Intervals
