Greedy algorithms for the shortest common superstring that are asymptotically optimal
ALAN M. FRIEZE, Wojciech Szpankowski · 2002
Various versions of the shortest common superstring (SCS) problem play important roles in data compression and DNA sequencing. For example, in laboratories DNA sequencing is routinely done by sequencing large numbers of relatively short fragments, and then heuristically finding a short common superstring. We assume that the input strings are independently generated, and we adopt a mixing model for the underlying probabilistic model of strings generation.