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

DOI10.4230/LIPIcs.CPM.2019.5OpenAlexW2954478296MaRDI QIDQ5088892

Binhai Zhu, Haitao Jiang, Jiong Guo, Daming 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)

Related Items (1)

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

Cites Work

• Unnamed Item
• 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
• On recovering syntenic blocks from comparative maps
• A linear kernel for the complementary maximal strip recovery problem
• An Improved Kernel for the Complementary Maximal Strip Recovery Problem
• Inapproximability of Maximal Strip Recovery: II
• Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms
• On Syntactic versus Computational Views of Approximability
• A 42k Kernel for the Complementary Maximal Strip Recovery Problem

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