Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring

Résumé

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.
Fichier principal
Vignette du fichier
2012.08878.pdf (125.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03442437 , version 1 (23-11-2021)

Identifiants

Citer

Bastien Cazaux, Eric Rivals. Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring. 2021. ⟨lirmm-03442437⟩
16 Consultations
13 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More