\boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring

DOI10.1137/S0097539796324661zbMath1051.68060MaRDI QIDQ4943853

Z. Sweedyk

Publication date: 19 March 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796324661

zbMATH Keywords

algorithm; data compression; shortest superstring; shotgun sequencing

Mathematics Subject Classification ID

68P10: Searching and sorting

68W05: Nonnumerical algorithms

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Related Items

Unnamed Item, Approximating Shortest Superstring Problem Using de Bruijn Graphs, CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM, On the readability of overlap digraphs, A probabilistic PTAS for shortest common superstring, Restricted and swap common superstring: a multivariate algorithmic perspective, Reoptimization of the shortest common superstring problem, The greedy algorithm for shortest superstrings, Minimum-weight cycle covers and their approximability, Why greed works for shortest common superstring problem, A \(2_3^2\) superstring approximation algorithm, A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem, A survey on combinatorial optimization in dynamic environments, On the Readability of Overlap Digraphs, On the Shortest Common Superstring of NGS Reads, Restricted Common Superstring and Restricted Common Supersequence, A Probabilistic PTAS for Shortest Common Superstring, Why Greed Works for Shortest Common Superstring Problem, Minimum-Weight Cycle Covers and Their Approximability, Reoptimization of the Shortest Common Superstring Problem