6533b85efe1ef96bd12bfe9f

RESEARCH PRODUCT

On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals

Tomasz KociumakaJakub RadoszewskiJakub RadoszewskiWojciech RytterGabriele FiciTomasz Waleń

subject

FOS: Computer and information sciences0102 computer and information sciences02 engineering and technologyInformation System01 natural sciencesString (physics)Theoretical Computer ScienceCombinatoricsHigh Energy Physics::TheoryAnalysis of algorithmGreedy algorithmComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringData Structures and Algorithms (cs.DS)Greedy algorithmFinite setAnalysis of algorithmsMathematicsSuperstring theoryShortest Common SuperstringComputer Science Applications1707 Computer Vision and Pattern RecognitionComputer Science ApplicationsReversalShortest Path Faster Algorithm010201 computation theory & mathematicsCompression ratioSignal Processing020201 artificial intelligence & image processingK shortest path routingInformation Systems

description

We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings $S$ is sought containing as a factor every string of $S$ or its reversal. We call this problem Shortest Common Superstring with Reversals (SCS-R). This problem has been introduced by Jiang et al., who designed a greedy-like algorithm with length approximation ratio $4$. In this paper, we show that a natural adaptation of the classical greedy algorithm for SCS has (optimal) compression ratio $\frac12$, i.e., the sum of the overlaps in the output string is at least half the sum of the overlaps in an optimal solution. We also provide a linear-time implementation of our algorithm.

yearjournalcountryeditionlanguage
2015-11-26
10.1016/j.ipl.2015.11.015http://arxiv.org/abs/1511.08431