Rotation of Periodic Strings and Short Superstrings
Dany Breslauer June 1996 |

## Abstract:This paper presents two simple approximation algorithms for the
shortest superstring problem, with approximation ratios
( ) and ( ), improving the best
previously published approximation. The framework of our
improved algorithms is similar to that of previous algorithms in the sense
that they construct a superstring by computing some optimal cycle covers on
the distance graph of the given strings, and then break and merge the cycles
to finally obtain a Hamiltonian path, but we make use of new bounds on the
overlap between two strings. We prove that for each periodic semi-infinite
string of period
Available as |

Last modified: 2003-06-08 by webmaster.