A greedy approximation algorithm for constructing shortest common superstrings

An approximation algorithm for the shortest common superstring problem is developed, based on the Knuth-Morris-Pratt string-matching procedure and on the greedy heuristics for finding longest Hamiltonian paths in weighted graphs. Given a set R of strings, the algorithm constructs a common superstring for R in O(mn) steps where m is the number of strings in R and n is the total length of these strings. The performance of the algorithm is analysed in terms of the compression in the common superstrings constructed, that is, in terms of n−k where k is the length of the obtained superstring. We show that (n−k)⩾ 1 2 (n−kmin) where k min is the length of a shortest common superstring. Hence the compression achieved by the algorithm is at least half of the maximum compression. It also seems that the lengths always satisfy k⩽2·k min but proving this remains open.

Authors

• Jorma Tarhio
• Esko Ukkonen

Keywords

No keywords are indexed for this paper.