Reversal distance for strings with duplicates: linear time approximation using hitting set
zbMATH Open1184.68641MaRDI QIDQ1010605FDOQ1010605
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
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
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
Protein sequences, DNA sequences (92D20) Searching and sorting (68P10) Approximation algorithms (68W25) Combinatorics on words (68R15)
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)
