Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set

DOI10.1007/11970125_22MaRDI QIDQ5443527zbMATH OpenOpenAlexFDO

Authors Petr Kolman, Tomasz Waleń

Publication date 21 February 2008

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11970125_22

zbMATH Keywords

Approximation algorithmsMinimum common string partitionSorting by reversalsString comparisonSuffix trees

Mathematics Subject Classification ID

Searching and sorting (68P10) Approximation algorithms (68W25)

Recommendations

• Reversal distance for strings with duplicates: linear time approximation using hitting set
• Mathematical Foundations of Computer Science 2005
• Approximating reversal distance for strings with bounded number of duplicates
• Sorting strings by reversals and by transpositions
• Reversal distances for strings with few blocks or small alphabets

Cited in

(18)

• Reversal distance for strings with duplicates: linear time approximation using hitting set
• Prefix and suffix reversals on strings
• Quick greedy computation for minimum common string partition
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• Solving the maximum duo-preservation string mapping problem with linear programming
• Mathematical programming strategies for solving the minimum common string partition problem
• Pattern matching with non overlapping reversals -- approximation and on-line algorithms
• Construct, Merge, Solve \& Adapt A new general algorithm for combinatorial optimization
• Adjacent Swaps on Strings
• Heuristics for reversal distance between genomes with duplicated genes
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• On the Approximability of Comparing Genomes with Duplicates
• Mathematical Foundations of Computer Science 2005
• Computational performance evaluation of two integer linear programming models for the minimum common string partition problem
• Signed rearrangement distances considering repeated genes, intergenic regions, and indels
• Minimum common string partition: on solving large‐scale problem instances
• Approximating reversal distance for strings with bounded number of duplicates

This page was built for publication: Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set

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