On the greedy algorithm for the Shortest Common Superstring problem with reversals
- Autori: Fici, G.; Kociumaka, T.; Radoszewski, J.; Rytter, W.; Waleń, T.
- Anno di pubblicazione: 2016
- Tipologia: Articolo in rivista (Articolo in rivista)
- Parole Chiave: Analysis of algorithms; Greedy algorithm; Reversal; Shortest Common Superstring; Information Systems; Computer Science Applications1707 Computer Vision and Pattern Recognition; Signal Processing; Theoretical Computer Science
- OA Link: http://hdl.handle.net/10447/191867
Abstract
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.