Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
From MaRDI portal
Publication:5443527
DOI10.1007/11970125_22zbMath1129.68431OpenAlexW1596864077MaRDI QIDQ5443527
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
Approximation algorithmsString comparisonSuffix treesSorting by reversalsMinimum common string partition
Related Items (14)
Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ Mathematical programming strategies for solving the minimum common string partition problem ⋮ Prefix and suffix reversals on strings ⋮ Construct, Merge, Solve \& Adapt A new general algorithm for combinatorial optimization ⋮ Signed rearrangement distances considering repeated genes, intergenic regions, and indels ⋮ Minimum common string partition: on solving large‐scale problem instances ⋮ Solving the maximum duo-preservation string mapping problem with linear programming ⋮ On the Approximability of Comparing Genomes with Duplicates ⋮ Sorting by Transpositions Is Difficult ⋮ Quick greedy computation for minimum common string partition ⋮ A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem ⋮ Computational performance evaluation of two integer linear programming models for the minimum common string partition problem ⋮ Unnamed Item ⋮ A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
This page was built for publication: Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set