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)

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

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)

Cited In (15)

• 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
• Faster implementation of a shortest superstring approximation
• Title not available (Why is that?)
• The greedy algorithm for shortest superstrings
• On the Shortest Common Superstring of NGS Reads
• A note on shortest superstrings with flipping
• Sequential and Parallel Approximation of Shortest Superstrings
• Linear approximation of shortest superstrings
• 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 that?)
• 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)