Parameterized tractability of the maximum-duo preservation string mapping problem
From MaRDI portal
Publication:306271
DOI10.1016/j.tcs.2016.07.011zbMath1348.68062DBLPjournals/tcs/0001CD16arXiv1512.03220OpenAlexW2964277875WikidataQ62044754 ScholiaQ62044754MaRDI QIDQ306271
Riccardo Dondi, Mauro Castelli, Stefano Beretta
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
Related Items (4)
Corrigendum to: ``Parameterized tractability of the maximum-duo preservation string mapping problem. ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem ⋮ A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- Variants of constrained longest common subsequence
- Minimum common string partition revisited
- Restricted and swap common superstring: a multivariate algorithmic perspective
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- 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
- Color-coding
- Improved Approximation for the Maximum Duo-Preservation String Mapping Problem
- Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Parameterized tractability of the maximum-duo preservation string mapping problem
