Approximating Shortest Superstrings

DOI10.1137/S0097539794286125MaRDI QIDQ4337677zbMATH OpenFDO

Authors Shang-Hua Teng, Frances F. Yao

Publication date 26 May 1997

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

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

zbMATH Keywords

approximation algorithmscombinatorial optimizationdata compressionDNA sequencingoptimal assignmentsthe shortest-superstring problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorics on words (68R15)

Recommendations

• Improved length bounds for the shortest superstring problem
• A 2_3² superstring approximation algorithm
• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• Linear approximation of shortest superstrings

Cited in

(25)

• A note on shortest superstrings with flipping
• A 2_3² superstring approximation algorithm
• Faster implementation of a shortest superstring approximation
• Parallel constructions of maximal path sets and applications to short superstrings
• A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
• The shortest superstring problem
• On the shortest common superstring of NGS reads
• Sequential and Parallel Approximation of Shortest Superstrings
• Reoptimization of the Shortest Common Superstring Problem
• Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model
• Linear approximation of shortest superstrings
• scientific article; zbMATH DE number 2079866 (Why is no real title available?)
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• Approximating shortest superstring problem using de Bruijn graphs
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• Parallel and sequential approximation of shortest superstrings
• Improved length bounds for the shortest superstring problem
• Practical lower and upper bounds for the shortest linear superstring
• Greedy shortest common superstring approximation in compact space
• Mathematical Foundations of Computer Science 2005
• Reoptimization of the shortest common superstring problem
• Shortest consistent superstrings computable in polynomial time
• Approximation guarantees for shortest superstrings: simpler and better
• On the extended binary Hamming code as a minor of optimal self-dual codes
• The greedy algorithm for shortest superstrings

This page was built for publication: Approximating Shortest Superstrings

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