APPROXIMATING SHORTEST SUPERSTRINGS

Authors
TENG SH YAO FF
Citation
Sh. Teng et Ff. Yao, APPROXIMATING SHORTEST SUPERSTRINGS, SIAM journal on computing, 26(2), 1997, pp. 410-417
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
26
Issue
2
Year of publication
1997
Pages
410 - 417
Database
ISI
SICI code
0097-5397(1997)26:2<410:ASS>2.0.ZU;2-F
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. Since the pr oblem is NP-hard and MAX SNP-hard, approximation algorithms are of int erest. We present a new algorithm which always finds a superstring tha t is at most 2.89 times as long as the shortest superstring. Our resul t improves the 3-approximation result of Blum et al.