Approximating Shortest Superstrings

DOI10.1137/S0097539794286125zbMATH Open0867.05044MaRDI QIDQ4337677FDOQ4337677

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^2\) superstring approximation algorithm
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Linear approximation of shortest superstrings

Cited In (20)

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