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

Gabriele Fici, Tomasz Waleń, Jakub Radoszewski, Tomasz Kociumaka, Wojciech Rytter

Risultato della ricerca: Articlepeer review

4 Citazioni (Scopus)

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.
Lingua originaleEnglish
pagine (da-a)245-251
Numero di pagine7
RivistaInformation Processing Letters
Volume116
Stato di pubblicazionePublished - 2016

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1711???
  • ???subjectarea.asjc.1700.1710???
  • ???subjectarea.asjc.1700.1706???

Fingerprint

Entra nei temi di ricerca di 'On the greedy algorithm for the Shortest Common Superstring problem with reversals'. Insieme formano una fingerprint unica.

Cita questo