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

DOI10.1007/11970125_22zbMath1129.68431OpenAlexW1596864077MaRDI QIDQ5443527

Petr Kolman, Tomasz Walen

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 algorithmsString comparisonSuffix treesSorting by reversalsMinimum common string partition

Mathematics Subject Classification ID

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

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