Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms

DOI10.1007/978-3-642-10631-6_72zbMath1273.68406OpenAlexW1490767057MaRDI QIDQ3652257

Laurent Bulteau, Guillaume Fertin, Irena Rusu

Publication date: 17 December 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_72

zbMATH Keywords

algorithmic complexityapproximation algorithmsgenome comparisonsynteny blockscomparative maps

Mathematics Subject Classification ID

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

Related Items (10)

On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ 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 ⋮ Tractability and approximability of maximal strip recovery ⋮ A linear kernel for the complementary maximal strip recovery problem ⋮ An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem ⋮ Tractability and Approximability of Maximal Strip Recovery ⋮ Inapproximability of maximal strip recovery ⋮ A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem

This page was built for publication: Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms