Approximating Shortest Superstrings

DOI10.1137/S0097539794286125zbMath0867.05044MaRDI QIDQ4337677

Frances F. Yao, Shang-Hua Teng

Publication date: 26 May 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

data compressioncombinatorial optimizationapproximation algorithmsDNA sequencingoptimal assignmentsthe shortest-superstring problem

Mathematics Subject Classification ID

Combinatorics on words (68R15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Faster implementation of a shortest superstring approximation, The greedy algorithm for shortest superstrings, Improved length bounds for the shortest superstring problem, On the Shortest Common Superstring of NGS Reads