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

DOI10.4230/LIPICS.CPM.2019.5OpenAlexW2954478296MaRDI QIDQ5088892FDOQ5088892

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/

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
• Inapproximability of maximal strip recovery

zbMATH Keywords

approximation algorithmlocal searchcomputational genomicsmaximal strip recoverycomplementary maximal strip recovery

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Title not available (Why is that?)
• On Syntactic versus Computational Views of Approximability
• On recovering syntenic blocks from comparative maps
• 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 kernel for the complementary maximal strip recovery problem
• A 42k Kernel for the Complementary Maximal Strip Recovery Problem

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)