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

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⟩
14 View
12 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More