Shortest common superstrings of random strings

DOI10.2307/3214990zbMATH Open0867.60002OpenAlexW4239580516MaRDI QIDQ3122874FDOQ3122874

Authors: Kenneth S. Alexander 

Publication date: 4 May 1997

Published in: Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/3214990

Recommendations

• The shortest common superstring problem: average case analysis for both exact and approximate matching
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Publication:4725747
• A probabilistic PTAS for shortest common superstring

zbMATH Keywords

entropydata compressionDNA sequencingpattern matchingshortest common superstring

Mathematics Subject Classification ID

Combinatorial probability (60C05) Combinatorics on words (68R15)

Cited In (3)

• Viral Genome Compression
• A Probabilistic PTAS for Shortest Common Superstring
• The shortest common superstring problem: average case analysis for both exact and approximate matching

This page was built for publication: Shortest common superstrings of random strings

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