A linear kernel for the complementary maximal strip recovery problem

DOI10.1016/J.JCSS.2014.03.005zbMATH Open1311.68205OpenAlexW2037515864MaRDI QIDQ2453554FDOQ2453554

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

Recommendations

• A linear kernel for the complementary maximal strip recovery problem
• An improved kernel for the complementary maximal strip recovery problem
• An improved linear kernel for complementary maximal strip recovery: simpler and smaller
• A \(42k\) kernel for the complementary maximal strip recovery problem
• Exact and approximation algorithms for the complementary maximal strip recovery problem

zbMATH Keywords

FPT algorithmkernelizationmaximum strip recovery

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Parametrized complexity theory.
• The complexity of theorem-proving procedures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• On recovering syntenic blocks from comparative maps
• Inapproximability of Maximal Strip Recovery: II
• 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
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Title not available (Why is that?)
• On Problems without Polynomial Kernels (Extended Abstract)

Cited In (4)

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

This page was built for publication: A linear kernel 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 Q2453554)