Prefix and suffix reversals on strings

DOI10.1016/j.dam.2017.07.031zbMath1453.68228OpenAlexW2751641127MaRDI QIDQ1647842

Géraldine Jean, Loïc Jankowiak, Guillaume Fertin

Publication date: 27 June 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.07.031

zbMATH Keywords

algorithmic complexitystringsapproximation algorithmsfixed-parameterized tractabilityprefix and suffix reversals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Prefix and suffix transreversals on binary and ternary strings
• Pancake flipping is hard
• Approximation algorithms for sorting by length-weighted prefix and suffix operations
• Bounds for sorting by prefix reversal
• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets
• Sorting Strings by Reversals and by Transpositions
• Prefix and Suffix Reversals on Strings
• Transforming cabbage into turnip
• Prefix Reversals on Binary and Ternary Strings
• Reversals and Transpositions Over Finite Alphabets
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set

This page was built for publication: Prefix and suffix reversals on strings