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

DOI10.1137/S0097539796324661MaRDI QIDQ4943853zbMATH OpenOpenAlexFDO

Authors 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

algorithmdata compressionshortest superstringshotgun sequencing

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1420898
• Approximation algorithms for the shortest common superstring problem
• Approximating shortest superstrings with constraints
• A greedy approximation algorithm for constructing shortest common superstrings
• A linear-time algorithm for finding approximate shortest common superstrings
• Improved length bounds for the shortest superstring problem
• Mathematical Foundations of Computer Science 2005
• Sequential and Parallel Approximation of Shortest Superstrings
• A 2_3² superstring approximation algorithm
• Parallel and sequential approximation of shortest superstrings

Cited in

(34)

• Minimum-weight cycle covers and their approximability
• Why greed works for shortest common superstring problem
• A 2_3² superstring approximation algorithm
• Approximating shortest superstrings with constraints
• Relationship between superstring and compression measures: new insights on the greedy conjecture
• Approximation algorithms for the shortest common superstring problem
• A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
• On the readability of overlap digraphs
• A survey on combinatorial optimization in dynamic environments
• On the Readability of Overlap Digraphs
• The shortest superstring problem
• On the shortest common superstring of NGS reads
• Restricted common superstring and restricted common supersequence
• Sequential and Parallel Approximation of Shortest Superstrings
• 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
• Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model
• A probabilistic PTAS for shortest common superstring
• Linear approximation of shortest superstrings
• Approximating Shortest Superstrings
• Rotations of Periodic Strings and Short Superstrings
• Approximating shortest superstring problem using de Bruijn graphs
• Restricted and swap common superstring: a multivariate algorithmic perspective
• scientific article; zbMATH DE number 7364999 (Why is no real title available?)
• Improved length bounds for the shortest superstring problem
• Greedy shortest common superstring approximation in compact space
• CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM
• Lyndon words and short superstrings
• Reoptimization of the shortest common superstring problem
• Approximation guarantees for shortest superstrings: simpler and better
• The greedy algorithm for shortest superstrings
• A linear-time algorithm for finding approximate shortest common superstrings

This page was built for publication: \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943853)