The shortest common superstring problem: average case analysis for both exact and approximate matching

DOI10.1109/18.782108zbMath0954.68079OpenAlexW2167057380MaRDI QIDQ4503372

Enhui Yang, Zhen Zhang

Publication date: 7 September 2000

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/18.782108

zbMATH Keywords

shortest common superstring problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25) Source coding (94A29)

Related Items (5)

A Probabilistic PTAS for Shortest Common Superstring ⋮ A probabilistic PTAS for shortest common superstring ⋮ Why Greed Works for Shortest Common Superstring Problem ⋮ Why greed works for shortest common superstring problem ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

This page was built for publication: The shortest common superstring problem: average case analysis for both exact and approximate matching