Why Greed Works for Shortest Common Superstring Problem

DOI10.1007/978-3-540-69068-9_23MaRDI QIDQ3506957zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Why greed works for shortest common superstring problem
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Linear approximation of shortest superstrings
• Approximating shortest superstrings with constraints

Cites work

• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• A greedy approximation algorithm for constructing shortest common superstrings
• An Algorithm for Reconstructing Protein and RNA Sequences
• Approximation algorithms for the shortest common superstring problem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• Linear approximation of shortest superstrings
• Mathematical Foundations of Computer Science 2005
• On finding minimal length superstrings
• Rotations of Periodic Strings and Short Superstrings
• Smoothed analysis of algorithms
• Smoothed analysis. Motivation and discrete models
• The greedy algorithm for shortest superstrings
• The shortest common superstring problem: average case analysis for both exact and approximate matching

Cited in

(7)

• Why greed works for shortest common superstring problem
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
• A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
• A Probabilistic PTAS for Shortest Common Superstring
• scientific article; zbMATH DE number 1973869 (Why is no real title available?)
• On the greedy algorithm for the shortest common superstring problem with reversals

This page was built for publication: Why Greed Works for Shortest Common Superstring Problem

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