Rotations of Periodic Strings and Short Superstrings

✍ Scribed by Dany Breslauer; Tao Jiang; Zhigen Jiang

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 219 KB
• Volume: 24
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0861

✦ Synopsis

This paper presents two simple approximation algorithms for the shortest 2 2 5 Ž . Ž . superstring problem with approximation ratios 2 f 2.67 and 2 f 2.596 . The 3 4 2

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 semiinfinite string ␣ s Ž . a a иии of period q, there exists an integer k, such that for any finite string s of 1 2 period p which is inequi¨alent to ␣, the overlap between s and the rotation 1 w x ␣ k s a a иии is at most p q q. Moreover, if p F q, then the overlap k kq1

2 2 w x Ž . between s and ␣ k is not larger than p q q . The bounds are tight. In the 3 Ž . previous shortest superstring algorithms p q q was used as the standard tight bound on overlap between two strings with periods p and q.