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)

zbMATH Keywords

combinatorial optimizationapproximation algorithmsdata 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

(20)

• Greedy shortest common superstring approximation in compact space
• Improved length bounds for the shortest superstring problem
• Sequential and Parallel Approximation of Shortest Superstrings
• Practical lower and upper bounds for the shortest linear superstring
• Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model
• Approximating shortest superstring problem using de Bruijn graphs
• Reoptimization of the shortest common superstring problem
• The greedy algorithm for shortest superstrings
• The shortest superstring problem
• A note on shortest superstrings with flipping
• scientific article; zbMATH DE number 2079866 (Why is no real title available?)
• On the shortest common superstring of NGS reads
• Reoptimization of the Shortest Common Superstring Problem
• Faster implementation of a shortest superstring approximation
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• Parallel and sequential approximation of shortest superstrings
• Linear approximation of shortest superstrings
• Mathematical Foundations of Computer Science 2005
• A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

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)