Shortest Common Superstrings of Random Strings

Autor: Alexander, Kenneth S.

Publikováno v: Journal of Applied Probability, 1996 Dec 01. 33(4), 1112-1126.

Externí odkaz: https://www.jstor.org/stable/3214990

All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent

Autor: Maksim S. Nikolaev

Publikováno v: String Processing and Information Retrieval ISBN: 9783030866914
SPIRE

In the Shortest Common Superstring problem (SCS), one needs to find the shortest superstring for a set of strings. While SCS is NP-hard and MAX-SNP-hard, the Greedy Algorithm “choose two strings with the largest overlap; merge them; repeat” achie

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::aaaac9fb8fe32e9f05efbb9fe022c264
https://doi.org/10.1007/978-3-030-86692-1_6

Relationship between superstring and compression measures: New insights on the greedy conjecture

Autor: Cazaux, Bastien, Rivals, Eric

Publikováno v: Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2018, 245, pp.59-64. ⟨10.1016/j.dam.2017.04.017⟩
Discrete Applied Mathematics, 2018, 245, pp.59-64. ⟨10.1016/j.dam.2017.04.017⟩

Earlier version as a report: lirmm-01070596v1; International audience; A superstring of a set of words is a string that contains each input word as a substring. Given such a set, the Shortest Superstring Problem (SSP) asks for a superstring of minimu

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::885a5ec2be0885a24a49023833495741
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01800340

Solving SCS for bounded length strings in fewer than steps

Autor: Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin

Publikováno v: Information Processing Letters. 114:421-425

It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O ⁎ ( 2 n ) time ( O ⁎ ( ⋅ ) suppresses polynomial factors of the input length). In this short note, we show that for any constant

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::f9242e8c0c878759d064e475dc62fa06
https://doi.org/10.1016/j.ipl.2014.03.004

On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals

Autor: Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Gabriele Fici, Tomasz Waleń

We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings $S$ is sought containing as a factor every string of $S$ or its reversal. We call this problem Shortest Common

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b8fc29c394f1b50a90f6f7aef085597b
http://arxiv.org/abs/1511.08431