A linear kernel for the complementary maximal strip recovery problem

DOI10.1016/j.jcss.2014.03.005zbMath1311.68205OpenAlexW2037515864MaRDI QIDQ2453554

Haitao Jiang, Binhai Zhu

Publication date: 10 June 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.03.005

zbMATH Keywords

FPT algorithmkernelizationmaximum strip recovery

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Genetics and epigenetics (92D10) Algorithms on strings (68W32)

Related Items

The complexity of finding common partitions of genomes with predefined block sizes, A 42k Kernel for the Complementary Maximal Strip Recovery Problem, A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem, An improved linear kernel for complementary maximal strip recovery: simpler and smaller

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Parametrized complexity theory.
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• On Problems without Polynomial Kernels (Extended Abstract)
• Inapproximability of Maximal Strip Recovery: II
• Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms
• Reducibility among Combinatorial Problems
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• The complexity of theorem-proving procedures