Approximating shortest superstrings with constraints

DOI10.1016/0304-3975(94)90249-6zbMath0834.68088OpenAlexW2011557376MaRDI QIDQ1341729

Ming Li, Tao Jiang

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)

Related Items (6)

DNA sequencing and string learning ⋮ Recognition of overlap graphs ⋮ A new graph model and algorithms for consistent superstring problems ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ Shortest consistent superstrings computable in polynomial time ⋮ A \(2_3^2\) superstring approximation algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of learning strings and sequences
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Approximation algorithms for the shortest common superstring problem
• A theory of the learnable

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