Why greed works for shortest common superstring problem

DOI10.1016/j.tcs.2009.09.014zbMath1187.68715OpenAlexW2111953579MaRDI QIDQ1038476

Bin Ma

Publication date: 18 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.09.014

zbMATH Keywords

smoothed analysisshortest common superstringpolynomial time approximation scheme

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Approximation algorithms (68W25)

Related Items (5)

A probabilistic PTAS for shortest common superstring ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ On the Shortest Common Superstring of NGS Reads ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ Practical lower and upper bounds for the Shortest Linear Superstring

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
• The Smoothed Complexity of Edit Distance
• 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

This page was built for publication: Why greed works for shortest common superstring problem