An improved linear kernel for complementary maximal strip recovery: simpler and smaller

DOI10.1016/J.TCS.2018.04.020MaRDI QIDQ2319903zbMATH OpenOpenAlexWikidataFDO

Authors Wen-Jun Li, Haiyan Liu, Jianxin Wang, L. Xiang, Yongjie Yang

Publication date 20 August 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.04.020

zbMATH Keywords

complementary maximal strip recoveryfixed-parameter tractablekernelizationlinear kernel

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Algorithms on strings (68W32)

Recommendations

• A 42k kernel for the complementary maximal strip recovery problem
• A linear kernel for the complementary maximal strip recovery problem
• An improved kernel for the complementary maximal strip recovery problem
• A linear kernel for the complementary maximal strip recovery problem
• Exact and approximation algorithms for the complementary maximal strip recovery problem

Cites work

• A 42k kernel for the complementary maximal strip recovery problem
• A linear kernel for the complementary maximal strip recovery problem
• An improved approximation algorithm for the complementary maximal strip recovery problem
• An improved kernel for the complementary maximal strip recovery problem
• Dealing with several parameterized problems by random methods
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved kernel results for some FPT problems based on simple observations
• Inapproximability of maximal strip recovery
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• On recovering syntenic blocks from comparative maps
• Partition on trees with supply and demand: kernelization and algorithms
• Planar graph vertex partition for linear problem kernels
• Towards optimal kernel for connected vertex cover in planar graphs
• Towards optimal kernel for edge-disjoint triangle packing
• Tractability and approximability of maximal strip recovery

Cited in

(7)

• The complexity of finding common partitions of genomes with predefined block sizes
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• An approximation algorithm for the \(l\)-pseudoforest deletion problem
• A linear kernel for the complementary maximal strip recovery problem
• 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

This page was built for publication: An improved linear kernel for complementary maximal strip recovery: simpler and smaller

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319903)