Maximal strip recovery problem with gaps: hardness and approximation algorithms
From MaRDI portal
Publication:2434927
DOI10.1016/j.jda.2012.12.006zbMath1280.68094OpenAlexW2007237784MaRDI QIDQ2434927
Guillaume Fertin, Laurent Bulteau, Irena Rusu
Publication date: 3 February 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2012.12.006
Analysis of algorithms (68W40) Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items (4)
The complexity of finding common partitions of genomes with predefined block sizes ⋮ A 42k Kernel for the Complementary Maximal Strip Recovery Problem ⋮ Finding a Small Number of Colourful Components ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact and approximation algorithms for the complementary maximal strip recovery problem
- An improved approximation algorithm for the complementary maximal strip recovery problem
- Inapproximability of maximal strip recovery
- Theory and applications of models of computation. 6th annual conference, TAMC 2009, Changsha, China, May 18--22, 2009. Proceedings
- On recovering syntenic blocks from comparative maps
- Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16--18, 2009. Proceedings
- On maximal independent sets of vertices in claw-free graphs
- Optimization, approximation, and complexity classes
- A constructive proof of Vizing's theorem
- Complexity of approximating bounded variants of optimization problems
- Minimum common string partition problem: hardness and approximations
- An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
- Tractability and Approximability of Maximal Strip Recovery
- Efficient Exact and Approximate Algorithms for the Complement of Maximal Strip Recovery
- Inapproximability of Maximal Strip Recovery: II
- Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems
- On the Tractability of Maximal Strip Recovery
- Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms
- Every planar map is four colorable
- On triangulating planar graphs under the four-connectivity constraint
- Scheduling Split Intervals
- On Recovering Syntenic Blocks from Comparative Maps
This page was built for publication: Maximal strip recovery problem with gaps: hardness and approximation algorithms
