Approximating shortest superstrings with constraints

DOI10.1016/0304-3975(94)90249-6MaRDI QIDQ1341729zbMATH OpenOpenAlexFDO

Authors Tao Jiang, Ming Li

Publication date 1 April 1996

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(94)90249-6

zbMATH Keywords

data compressionDNA sequencingshortest common superstring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Approximating shortest superstrings with constraints
• Linear approximation of shortest superstrings
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• A 2_3² superstring approximation algorithm

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• A theory of the learnable
• Approximation algorithms for the shortest common superstring problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3272833 (Why is no real title available?)
• On finding minimal length superstrings
• On the complexity of learning strings and sequences

Cited in

(16)

• A note on shortest superstrings with flipping
• A 2_3² superstring approximation algorithm
• A linear time algorithm for shortest cyclic cover of strings
• A new graph model and algorithms for consistent superstring problems
• Sequential and Parallel Approximation of Shortest Superstrings
• The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings
• DNA sequencing and string learning
• Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model
• Recognition of overlap graphs
• Linear approximation of shortest superstrings
• Approximating shortest superstrings with constraints
• Superstrings with multiplicities
• Shortest consistent superstrings computable in polynomial time
• Constructions of covering sequences and 2D-sequences
• On the greedy algorithm for the shortest common superstring problem with reversals
• A linear-time algorithm for finding approximate shortest common superstrings

This page was built for publication: Approximating shortest superstrings with constraints

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