TY - JOUR

T1 - On the greedy algorithm for the Shortest Common Superstring problem with reversals

AU - Fici, Gabriele

AU - Waleń, Tomasz

AU - Radoszewski, Jakub

AU - Kociumaka, Tomasz

AU - Rytter, Wojciech

PY - 2016

Y1 - 2016

N2 - 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. [9], 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 12, 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.

AB - 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. [9], 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 12, 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.

KW - Analysis of algorithms

KW - Computer Science Applications1707 Computer Vision and Pattern Recognition

KW - Greedy algorithm

KW - Information Systems

KW - Reversal

KW - Shortest Common Superstring

KW - Signal Processing

KW - Theoretical Computer Science

KW - Analysis of algorithms

KW - Computer Science Applications1707 Computer Vision and Pattern Recognition

KW - Greedy algorithm

KW - Information Systems

KW - Reversal

KW - Shortest Common Superstring

KW - Signal Processing

KW - Theoretical Computer Science

UR - http://hdl.handle.net/10447/191867

M3 - Article

VL - 116

SP - 245

EP - 251

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

ER -