Revisiting the parameterized complexity of maximum-duo preservation string mapping

DOI10.1016/j.tcs.2020.09.034zbMath1464.68445OpenAlexW3088381880MaRDI QIDQ2210511

Meirav Zehavi, Christian Komusiewicz, Mateus de Oliveira Oliveira

Publication date: 6 November 2020

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7343/

zbMATH Keywords

parameterized algorithmskernelizationmaximum-duo preservation string mapping

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Genetics and epigenetics (92D10) Randomized algorithms (68W20) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Corrigendum to: ``Parameterized tractability of the maximum-duo preservation string mapping problem.
• Fundamentals of parameterized complexity
• Minimum common string partition revisited
• Representative families: a unified tradeoff-based approach
• A probabilistic remark on algebraic program testing
• Further improvement in approximating the maximum duo-preservation string mapping problem
• Narrow sieves for parameterized paths and packings
• Solving the maximum duo-preservation string mapping problem with linear programming
• Minimum common string partition problem: hardness and approximations
• The string edit distance matching problem with moves
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Algorithms on Strings, Trees and Sequences
• Kernelization
• Improved Approximation for the Maximum Duo-Preservation String Mapping Problem
• Approximating the true evolutionary distance between two genomes
• A 7/2-approximation algorithm for the Maximum Duo-Preservation String Mapping Problem
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Determinant Sums for Undirected Hamiltonicity
• Algorithms on Strings
• Parameterized Algorithms

This page was built for publication: Revisiting the parameterized complexity of maximum-duo preservation string mapping