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

DOI10.1016/j.tcs.2018.04.020zbMath1429.68340OpenAlexW2802367975WikidataQ129967247 ScholiaQ129967247MaRDI QIDQ2319903

Jianxin Wang, Yongjie Yang, Wenjun Li, Haiyan Liu, Lingyun Xiang

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

kernelizationfixed-parameter tractablelinear kernelcomplementary maximal strip recovery

Mathematics Subject Classification ID

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

Related Items (3)

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

Cites Work

• Unnamed Item
• Planar graph vertex partition for linear problem kernels
• Fundamentals of parameterized complexity
• 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
• Partition on trees with supply and demand: kernelization and algorithms
• Improved kernel results for some FPT problems based on simple observations
• Inapproximability of maximal strip recovery
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On recovering syntenic blocks from comparative maps
• Towards optimal kernel for connected vertex cover in planar graphs
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Towards optimal kernel for edge-disjoint triangle packing
• A linear kernel for the complementary maximal strip recovery problem
• Dealing with several parameterized problems by random methods
• An Improved Kernel for the Complementary Maximal Strip Recovery Problem
• A 42k Kernel for the Complementary Maximal Strip Recovery Problem
• Fixed-Parameter Tractability and Completeness I: Basic Results

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