Rotation of Periodic Strings and Short Superstrings

Dany Breslauer
Tao Jiang
Zhigen Jiang

June 1996


This paper presents two simple approximation algorithms for the shortest superstring problem, with approximation ratios tex2html_wrap_inline28 ( tex2html_wrap_inline30 ) and tex2html_wrap_inline32 ( tex2html_wrap_inline34 ), improving the best previously published tex2html_wrap_inline36 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 tex2html_wrap_inline38 of period q, there exists an integer k, such that for any (finite) string s of period p which is inequivalent to tex2html_wrap_inline48 , the overlap between s and the rotation tex2html_wrap_inline52 is at most tex2html_wrap_inline54 . Moreover, if tex2html_wrap_inline56 , then the overlap between s and tex2html_wrap_inline60 is not larger than tex2html_wrap_inline62 . In the previous shortest superstring algorithms p+q was used as the standard bound on overlap between two strings with periods p and q.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.