Why Greed Works for Shortest Common Superstring Problem

DOI10.1007/978-3-540-69068-9_23zbMath1143.68640OpenAlexW2129525792MaRDI QIDQ3506957

Bin Ma

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69068-9_23

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items

A Probabilistic PTAS for Shortest Common Superstring ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

Cites Work

• Unnamed Item
• The greedy algorithm for shortest superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Approximation algorithms for the shortest common superstring problem
• Smoothed analysis of algorithms
• Linear approximation of shortest superstrings
• Rotations of Periodic Strings and Short Superstrings
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Mathematical Foundations of Computer Science 2005
• An Algorithm for Reconstructing Protein and RNA Sequences
• Algorithms and Data Structures