Parameterized tractability of the maximum-duo preservation string mapping problem

DOI10.1016/J.TCS.2016.07.011MaRDI QIDQ306271zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Stefano Beretta, Mauro Castelli, Riccardo Dondi

Publication date 31 August 2016

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

Full work available at URL https://arxiv.org/abs/1512.03220

zbMATH Keywords

computational biologykernelizationparameterized algorithmscommon string partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O(k^6 ).

Recommendations

• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• A family of approximation algorithms for the maximum duo-preservation string mapping problem
• Corrigendum to: ``Parameterized tractability of the maximum-duo preservation string mapping problem.
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Color-coding
• Fixed-parameter algorithms for scaffold filling
• Fundamentals of parameterized complexity
• Improved approximation for the maximum duo-preservation string mapping problem
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Minimum common string partition problem: hardness and approximations
• Minimum common string partition revisited
• Restricted and swap common superstring: a multivariate algorithmic perspective
• Reversal distance for strings with duplicates: linear time approximation using hitting set
• Solving the maximum duo-preservation string mapping problem with linear programming
• The greedy algorithm for the minimum common string partition problem
• The string edit distance matching problem with moves
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Variants of constrained longest common subsequence

Cited in

(5)

• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• Corrigendum to: ``Parameterized tractability of the maximum-duo preservation string mapping problem.
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• Revisiting the parameterized complexity of maximum-duo preservation string mapping

This page was built for publication: Parameterized tractability of the maximum-duo preservation string mapping problem

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