Skip to Main content Skip to Navigation
Conference papers

Algorithms for Three Versions of the Shortest Common Superstring Problem

Abstract : The input to the Shortest Common Superstring (SCS) problem is a set S of k words of total length n. In the classical version the output is an explicit word SCS(S) in which each s in S occurs at least once. In our paper we consider two versions with multiple occurrences, in which the input includes additional numbers (multiplicities), given in binary. Our output is the word SCS(S) given implicitly in a compact form, since its real size could be exponential. We also consider a case when all input words are of length two, where our main algorithmic tool is a compact representation of Eulerian cycles in multigraphs. Due to exponential multiplicities of edges such cycles can be exponential and the compact representation is needed. Other tools used in our paper are a polynomial case of integer linear programming and a min-plus product of matrices.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00742040
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 10:21:57 AM
Last modification on : Monday, June 8, 2020 - 10:54:02 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:17 AM

File

Algorithms_for_Three_Versions_...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00742040, version 1

Citation

Maxime Crochemore, Marek Cygan, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, et al.. Algorithms for Three Versions of the Shortest Common Superstring Problem. CPM, 2010, New-York, United States. pp.299-309. ⟨hal-00742040⟩

Share

Metrics

Record views

452

Files downloads

513