Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Preprints, Working Papers, ... Year : 2021

Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring

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.
Fichier principal
Vignette du fichier
2012.08878.pdf (125.99 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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

Altmetric

Share

More