\boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
From MaRDI portal
Publication:4943853
DOI10.1137/S0097539796324661zbMath1051.68060OpenAlexW2037050365MaRDI QIDQ4943853
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
Searching and sorting (68P10) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Related Items (20)
On the readability of overlap digraphs ⋮ The greedy algorithm for shortest superstrings ⋮ A survey on combinatorial optimization in dynamic environments ⋮ A Probabilistic PTAS for Shortest Common Superstring ⋮ On the Readability of Overlap Digraphs ⋮ A probabilistic PTAS for shortest common superstring ⋮ Unnamed Item ⋮ Why Greed Works for Shortest Common Superstring Problem ⋮ Minimum-Weight Cycle Covers and Their Approximability ⋮ Reoptimization of the shortest common superstring problem ⋮ On the Shortest Common Superstring of NGS Reads ⋮ Restricted and swap common superstring: a multivariate algorithmic perspective ⋮ Restricted Common Superstring and Restricted Common Supersequence ⋮ CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ Minimum-weight cycle covers and their approximability ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ Why greed works for shortest common superstring problem ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
This page was built for publication: \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
