A linear kernel for the complementary maximal strip recovery problem

DOI10.1016/J.JCSS.2014.03.005MaRDI QIDQ2453554zbMATH OpenOpenAlexFDO

Authors 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

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

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

Cites work

• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• An improved approximation algorithm 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 Problems without Polynomial Kernels (Extended Abstract)
• On recovering syntenic blocks from comparative maps
• Parametrized complexity theory.
• Reducibility among combinatorial problems
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• The complexity of theorem-proving procedures
• Tractability and approximability of maximal strip recovery
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited in

(7)

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

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)