A Probabilistic PTAS for Shortest Common Superstring
From MaRDI portal
Publication:3182960
DOI10.1007/978-3-642-03816-7_53zbMath1250.68286OpenAlexW1494513742MaRDI QIDQ3182960
Publication date: 16 October 2009
Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_53
Cites Work
- Unnamed Item
- A greedy approximation algorithm for constructing shortest common superstrings
- More on the complexity of common superstring and supersequence problems
- Greedy algorithms for the shortest common superstring that are asymptotically optimal
- Approximation algorithms for the shortest common superstring problem
- Why Greed Works for Shortest Common Superstring Problem
- Algorithms on Strings, Trees and Sequences
- Linear approximation of shortest superstrings
- The shortest common superstring problem: average case analysis for both exact and approximate matching
- \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
- Smoothed analysis of algorithms
- Mathematical Foundations of Computer Science 2005