Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring

Bastien Cazaux 1 Eric Rivals 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A superstring of a set of strings correspond to a string which contains all the other strings as substrings. The problem of finding the Shortest Linear Superstring is a well-know and wellstudied problem in stringology. We present here a variant of this problem, the Shortest Circular Superstring problem where the sought superstring is a circular string. We show a strong link between these two problems and prove that the Shortest Circular Superstring problem is NPcomplete. Moreover, we propose a new conjecture on the approximation ratio of the Shortest Circular Superstring problem.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03442437
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Tuesday, November 23, 2021 - 10:35:24 AM
Last modification on : Wednesday, November 24, 2021 - 3:48:35 AM

File

2012.08878.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-03442437, version 1
  • ARXIV : 2012.08878

Collections

Citation

Bastien Cazaux, Eric Rivals. Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring. 2021. ⟨lirmm-03442437⟩

Share

Metrics

Record views

8

Files downloads

1