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

MaRDI QIDQ1010605zbMATH OpenFDO

Authors Petr Kolman, Tomasz Waleń

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, http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r50.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

string comparisonMinimum Common String Partition Problem

Mathematics Subject Classification ID

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

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
• Reversal distances for strings with few blocks or small alphabets
• A new distance metric on strings computable in linear time
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Almost linear time computation of maximal repetitions in run length encoded strings
• Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
• scientific article; zbMATH DE number 826062

Cited in

(6)

• Mathematical Foundations of Computer Science 2005
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Approximating reversal distance for strings with bounded number of duplicates
• Minimum common string partition revisited
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• 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

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