Approximating Shortest Superstrings
- 1 March 1997
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 26 (2) , 410-417
- https://doi.org/10.1137/s0097539794286125
Abstract
The Shortest Superstring Problem is to find a shortest possible string that contains every string in a given set as substrings. This problem has applications to data compression and DNA sequencing. As the problem is NP-hard and MAX SNP-hard, approximation algorithms are of interest. We present a new algorithm which always finds a superstring that is at most 2.89 times as long as the shortest superstring. Our result improves the 3-approximation result of Blum, Jiang, Li, Tromp, and Yannakakis (1991).Keywords
This publication has 9 references indexed in Scilit:
- Approximation algorithms for the shortest common superstring problemInformation and Computation, 1989
- A greedy approximation algorithm for constructing shortest common superstringsTheoretical Computer Science, 1988
- Data Structures and Network AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1983
- Data compression via textual substitutionJournal of the ACM, 1982
- On finding minimal length superstringsJournal of Computer and System Sciences, 1980
- Computer programs for the assembly of DNA sequencesNucleic Acids Research, 1979
- Information compression by factorising common stringsThe Computer Journal, 1975
- An Algorithm for Reconstructing Protein and RNA SequencesJournal of the ACM, 1967
- Uniqueness theorems for periodic functionsProceedings of the American Mathematical Society, 1965