Parameterized tractability of the maximum-duo preservation string mapping problem

DOI10.1016/J.TCS.2016.07.011zbMATH Open1348.68062DBLPjournals/tcs/0001CD16arXiv1512.03220OpenAlexW2964277875WikidataQ62044754 ScholiaQ62044754MaRDI QIDQ306271FDOQ306271

Riccardo Dondi, Mauro Castelli, Stefano Beretta

Publication date: 31 August 2016

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

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 ).

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

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

zbMATH Keywords

computational biologykernelizationparameterized algorithmscommon string partition

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• 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

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)