Maximal strip recovery problem with gaps: hardness and approximation algorithms

DOI10.1007/978-3-642-10631-6_72MaRDI QIDQ3652257zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsalgorithmic complexitygenome comparisonsynteny blockscomparative maps

Mathematics Subject Classification ID

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

Recommendations

• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Inapproximability of maximal strip recovery
• Tractability and approximability of maximal strip recovery
• Tractability and approximability of maximal strip recovery

Cited in

(10)

• 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
• An improved approximation algorithm for the complementary maximal strip recovery problem
• Tractability and approximability of maximal strip recovery
• Inapproximability of maximal strip recovery
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• An improved approximation algorithm for the complementary maximal strip recovery problem
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• A linear kernel for the complementary maximal strip recovery problem

This page was built for publication: Maximal strip recovery problem with gaps: hardness and approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3652257)