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⟩
20 Consultations
16 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More