A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem

DOI10.4230/LIPICS.CPM.2019.5MaRDI QIDQ5088892zbMATH OpenOpenAlexFDO

Authors Haitao Jiang, Jiong Guo, Daming Zhu, Binhai Zhu

Publication date 18 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10476/pdf/LIPIcs-CPM-2019-5.pdf/

zbMATH Keywords

approximation algorithmlocal searchcomputational genomicsmaximal strip recoverycomplementary maximal strip recovery

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• An improved approximation algorithm for the complementary maximal strip recovery problem
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• Efficient exact and approximate algorithms for the complement of Maximal Strip Recovery
• Inapproximability of maximal strip recovery

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 42k Kernel for the Complementary Maximal Strip Recovery Problem
• A linear kernel for the complementary maximal strip recovery problem
• An improved approximation algorithm for the complementary maximal strip recovery problem
• An improved kernel for the complementary maximal strip recovery problem
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• On Syntactic versus Computational Views of Approximability
• On recovering syntenic blocks from comparative maps
• Tractability and approximability of maximal strip recovery

Cited in

(1)

• The complexity of finding common partitions of genomes with predefined block sizes

This page was built for publication: A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem

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