Reversal distance for strings with duplicates: linear time approximation using hitting set

zbMath1184.68641MaRDI QIDQ1010605

Tomasz Walen, Petr Kolman

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/117182

zbMATH Keywords

string comparisonMinimum Common String Partition Problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics on words (68R15) Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25)

Related Items (3)

Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ Minimum common string partition revisited ⋮ Quick Greedy Computation for Minimum Common String Partitions

This page was built for publication: Reversal distance for strings with duplicates: linear time approximation using hitting set