The greedy algorithm for shortest superstrings

DOI10.1016/j.ipl.2004.09.012zbMath1173.68885OpenAlexW2076047621MaRDI QIDQ834977

Nira Shafrir, Haim Kaplan

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.09.012

zbMATH Keywords

algorithmsanalysis of algorithmsapproximation algorithmsshortest superstring

Mathematics Subject Classification ID

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

Related Items (14)

The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ Non-uniqueness of minimal superpermutations ⋮ A probabilistic PTAS for shortest common superstring ⋮ Why Greed Works for Shortest Common Superstring Problem ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ Reoptimization of the shortest common superstring problem ⋮ On the Shortest Common Superstring of NGS Reads ⋮ Collapsing Superstring Conjecture ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Why greed works for shortest common superstring problem ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

Cites Work

• Sequential and Parallel Approximation of Shortest Superstrings
• Linear approximation of shortest superstrings
• Approximating Shortest Superstrings
• Rotations of Periodic Strings and Short Superstrings
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Improved length bounds for the shortest superstring problem

This page was built for publication: The greedy algorithm for shortest superstrings